#include <bits/stdc++.h>
using namespace std;
using P = pair<int, long long>;

int main() {
  long long n,m;
  long long a,b,c,d;
  cin >> n >> m;
  vector<vector<long long>> data;
  vector<vector<long>> path(n,vector<long>());
  for(int i=0;i<m;i++) {
    cin >> a >> b >> c >> d;
    a--; b--;
    data.push_back({a,b,c,d,(long long)(sqrt(d*1.0)+0.5)-1});
    path[a].push_back({i});
    path[b].push_back({i});
  }
  bitset<101010> flag;
  stack<int> st;
  st.push(0);
  int now, next;
  while(!st.empty()){
    now = st.top();
    st.pop();
    flag[now]=true;
    for(int i=0;i<path[now].size();i++){
      if(data[path[now][i]][0]==now) next = data[path[now][i]][1];
      else next = data[path[now][i]][0];
      if(!flag[next])flag[next]=1, st.push(next);
    }
  }
  if(!flag[n-1]) {
    cout << "-1" << endl;
    return 0;
  }
  vector<long long> dis(n, 1000000000000000LL);
  dis[0]=0;
  auto comp = [](P l, P r) { return l.second>r.second; };
  priority_queue<P, vector<P>, decltype(comp)> q(comp);
  q.push({0,0});
  pair<int,long long> u;
  long long tmin;
  int to;
  while(!q.empty()){
    u=q.top();
    q.pop();
    now=u.first;
    if(dis[now]<u.second) continue;
    for(int i=0;i<path[now].size();i++){
      to=path[now][i];
      tmin=data[to][2];
      if(u.second<=data[to][4]){
        tmin+=data[to][4]+data[to][3]/(data[to][4]+1);
      } else {
        tmin+=u.second+data[to][3]/(u.second+1);
      }
      if(data[path[now][i]][0]==now) next = data[path[now][i]][1];
      else next = data[path[now][i]][0];
      if(tmin<dis[next]){
        dis[next]=tmin;
        q.push({next,tmin});
      }
    }
  }
  cout << dis[n-1] << endl;
}
//https://atcoder.jp/contests/abc188/tasks/abc188_d
#include <bits/stdc++.h>
using namespace std;
#define F first 
#define S second
typedef long long ll;
typedef long double ld;
const ll mod = 1e9 + 7;

int main ()
{
    ios_base::sync_with_stdio (0); cin.tie (0); cout.tie (0);
    ll n, c, ans = 0;
    cin >> n >> c;
    vector<pair<ll, ll>> v;
    for (ll i = 0; i < n; ++i)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        v.push_back ({a - 1, c});
        v.push_back ({b, -c});
    }
    sort (v.begin (), v.end ());
    ll t = 0, p = 0;
    for (auto& x : v)
    {
        if (x.F != t)
        {
            ans += min (c, p) * (x.F - t);
            t = x.F;
        }
        p += x.S;
    }
    cout << ans;
}

