#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
typedef long long ll;
using namespace std;
const ll INF = 1e18;

struct edge {
    ll to;
    ll cost;
    ll d;
};
using P = pair<ll, ll>;
vector<vector<edge>> G;
vector<ll> d;
void dijkstra(int s) {
    priority_queue<P, vector<P>, greater<P>> que;
    fill(d.begin(), d.end(), INF);
    d[s] = 0;
    que.push(P(0, s));
    while (!que.empty()) {
        P p = que.top();
        que.pop();
        int v = p.second;
        if (d[v] < p.first)
            continue;
        rep(i, G[v].size()) {
            edge e = G[v][i];

            ll sq = sqrt(e.d);
            if (sq * sq != e.d) sq++;
            sq--;

            ll cost = 0;
            if (d[v] < sq)
                cost = sq - d[v] + e.cost + e.d / (sq + 1);
            else
                cost = e.cost + e.d / (d[v] + 1);

            if (d[e.to] > d[v] + cost) {
                d[e.to] = d[v] + cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    cin >> N >> M;
    G.resize(N);
    d.resize(N);
    rep(i, M) {
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        a--, b--;
        G[a].push_back({b, c, d});
        G[b].push_back({a, c, d});
    }

    dijkstra(0);
    ll ans = d[N - 1];

    if (ans == INF)
        cout << -1 << endl;
    else
        cout << ans << endl;

    return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long

int n,m;
vector<int> a,b;
vector<ll> c,d;
vector<vector<int>> links;
vector<ll> earliest;
priority_queue<pair<ll,int>, vector<pair<ll,int>>,greater<pair<ll,int>>> q;

void initialize(){
  cin >> n >> m;
  links.resize(n,vector<int>(0));
  earliest.resize(n,-1);
  a.resize(m);
  b.resize(m);
  c.resize(m);
  d.resize(m);
  for(int i=0; i<m; i++){
    cin >> a[i] >> b[i] >> c[i] >> d[i];
    links[a[i]-1].push_back(i);
    links[b[i]-1].push_back(i);
  }
}

/*
template <typename T> void print_vv(vector<vector<T>> &vv){
  for(int i=0;i<vv.size();i++){
    cout << i << " * ";
    for(auto& j:vv[i]) cout << j << ' ';
    cout << endl;
  }
}
template <typename T> void print_v(vector<T> &a){
  cout << "{ ";
  for(auto& i:a) cout << i << ' ';
  cout << '}' << endl;
}*/

ll fastest(ll di,ll start){
  //cout << "fastest " << di << ' ' << start << " : ";
  ll t = max(start,(ll)round(sqrt(di))-2);
  ll i=di/(t+1)+t;
  while(i>di/(t+2)+t+1){
    t ++;
    i = di/(t+1)+t;
  }
  //cout << i << endl;
  return i;
}


int main(){

  initialize();
  /*
  print_vv(links);
  print_v(c);
  print_v(d);
  print_v(earliest);
  */
  q.push( {0, 0} );
  
  while(q.size()>0){

    auto node = q.top();
    q.pop();
    if(earliest[node.second] != -1) continue;
    earliest[node.second] = node.first;
    //cout << node.second << ' ' << node.first << endl;

    for(auto& i : links[node.second]){
      int tmp = (a[i]-1 == node.second ? b[i]-1 : a[i]-1);
      q.push( {c[i]+fastest(d[i], node.first), tmp} );
    }
    
    //print_v(earliest);
    
  }

  cout << earliest[n-1] << endl;
}
