#include <bits/extc++.h>
using namespace std;
using ll = long long;
#define REP(i,n) for(int i=0;i<int(n);i++)
#define FOR(i,a,b) for(int i=a;i<=int(b);i++)
#define ALL(x) x.begin(),x.end()

vector<vector<tuple<int, ll, ll, ll>>> gr;
vector<ll> ans;
signed main() {
  int n, m;
  ll inf = 1000100010001000;
  cin >> n >> m;
  priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
  gr.resize(n);
  ans.resize(n, inf);
  REP(i, m){
    int a, b;
    double c, d;
    cin >> a >> b >> c >> d;
    a--;b--;
    ll t = (ll)((sqrt(1 + 4 * d) - 1) / 2);
    if(a==b)continue;
    gr[a].push_back({b, (ll)c, (ll)d,  t});
    gr[b].push_back({a, (ll)c, (ll)d,  t});
  }
  
  pq.push({0, 0});
  while(!pq.empty()){
    ll now = pq.top().first;
    int x = pq.top().second;
    pq.pop();
    if (ans[x] < now)continue;
    for(auto tap: gr[x]){
      
      int to = get<0>(tap);
      ll c = get<1>(tap);
      ll d = get<2>(tap); 
      ll t = get<3>(tap);
      if(t>now){
        ll cost = t + c + d / (t + 1);
        if(cost < ans[to]){
          ans[to] = cost;
          pq.push({ans[to], to});   
        } 
      } else {
        ll cost = now + c + d / (now+1);
        if(cost < ans[to]){
          ans[to] = cost;   
          pq.push({ans[to], to});           
        }
      }
    }
    
  }
  if(ans[n-1]==inf){
    cout << -1;
  }else{
    cout << ans[n-1];
  }



  return 0;
}
#include <bits/stdc++.h>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ld long double
#define ll long long
using namespace std;

#define MOD 1000000007
#define INF 100000000000000000

ll calc(ll currTime, ll waitTime, ll edgeCost) {
    return waitTime + edgeCost / (currTime + waitTime + 1);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    // {dest, {c, d}}
    vector<vector<pair<ll, pll>>> edges(n + 1);
    
    for (int i = 0; i < m; i++) {
        ll u, v, c, d;
        cin >> u >> v >> c >> d;
        edges[u].push_back({v, {c, d}});
        edges[v].push_back({u, {c, d}});
    }
    
    vector<ll> dist(n + 1, INF);
    dist[1] = 0;
    // {{time, city}}
    priority_queue<pll, vector<pll>, greater<pll>> q;
    q.push({0, 1});
    while (!q.empty()) {
        pll p = q.top();
        q.pop();
        ll node = p.second;
        ll currTime = p.first;
        if (currTime > dist[node]) continue;
        
        for (auto edge : edges[node]) {
            ll dest = edge.first;
            // edgeCost = c + bs(currTime, d)
            ll waitTime = calc(currTime, 0, edge.second.second);
            ll critPoint = sqrt(edge.second.second) - currTime - 1;
            
            for (ll i = max(0LL, critPoint - 3); i <= max(0LL, critPoint + 3); i++) {
                waitTime = min(waitTime, calc(currTime, i, edge.second.second));
            }
            
//            ll edgeCost = edge.second.first + waitTime + edge.second.second / (currTime + waitTime + 1);
            ll edgeCost = edge.second.first + waitTime;
            if (dist[node] + edgeCost < dist[dest]) {
                q.push({dist[node] + edgeCost, dest});
                dist[dest] = dist[node] + edgeCost;
            }
        }
    }
    
//    cout << 1 + calc(0, 89, 10000) << '\n';
    if (dist[n] >= INF) cout << "-1\n";
    else cout << dist[n] << '\n';
    
    
}

/*
 2 1
 1 2 1 10000
 */
