#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

struct edge{
  ll to, c, d;
};

int main(){
  int n, m;
  cin >> n >> m;
  vector<vector<edge>> G(n);
  for(int i = 0; i < m; i++){
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    a--; b--;
    G[a].push_back((edge){b, c, d});
    G[b].push_back((edge){a, c, d});
  }
  priority_queue<P, vector<P>, greater<P>> todo;
  todo.push(P(0, 0));
  vector<ll> dist(n, 1e16);
  dist[0] = 0;
  while(!todo.empty()){
    P now = todo.top(); todo.pop();
    ll pos = now.second;
    if(pos == n - 1) break;
    ll t = now.first;
    if(t > dist[pos]) continue;
    for(int i = 0; i < G[pos].size(); i++){
      edge e = G[pos][i];
      ll nxt = e.to;
      ll c = e.c;
      ll d = e.d;
      ll time = sqrt(d);
      if(t >= time) time = t;
      ll arrive = c + time + d / (time + 1);
      if(dist[nxt] > arrive){
        dist[nxt] = arrive;
        todo.push(P(arrive, nxt));
      }
    }
  }
  if(dist[n - 1] == 1e16) cout << -1 << endl;
  else cout << dist[n - 1] << endl;
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int,int>
#define vpii vector<pair<int,int>>
#define pqueue priority_queue
#define umap unordered_map
#define uset unordered_set
#define bit(s, i) ((1 << i) & s ? 1 : 0)
#define bits(x) __builtin_popcount((x))
#define gcd(x, y) __gcd(x, y)
#define lcm(x, y) ((x) / gcd(x, y) * (y))
#define inf 4557430888798830399LL
#define mst(dp, val) memset(dp, val, sizeof(dp))
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define repd(i, a, b, d) for (int i = a; i <= b; i += d)
#define rep_(i, a, b) for (int i = a; i >= b; --i)
#define repd_(i, a, b) for (int i = a; i >= b; i -= d)
#define mxm(a, b) a = max(a, b) 
#define mnm(a, b) a = min(a, b)
#define pb push_back
#define X first
#define Y second
#define all(x) (x).begin(), (x).end()
#define debug(x) cout << #x << "=" << x << endl
#define readArr(a, n) for (int i = 1; i <= n; i++) cin >> a[i];
#define printArr(a, n) for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl;
#define print(e) cout << (e) << endl
const int mod = 1e9 + 7;
#define Add(x, val) x = (x + (val)) % mod
// #define MULTI_CASES
// #define PRE

const int N = 1e5 + 5;
struct Edge {
    int v, c, d;
};
using Node = pii; //距离，节点编号
vector<Edge> g[N];

void solve() {
    int n, m;
    cin >> n >> m;
    rep(i, 1, m) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        g[u].pb({v, c, d});
        g[v].pb({u, c, d});
    }
    vi dist(n+1, inf);
    vi vis(n+1);
    pqueue<Node, vector<Node>, greater<Node>> q;
    q.push({0, 1});
    dist[1] = 0;
    while (!q.empty()) {
        int u = q.top().Y, t = q.top().X;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto e : g[u]) {
            int v = e.v, c = e.c, d = e.d;

            if (t + c + d / (t + 1) < dist[v]) {
                dist[v] = t + c + d / (t + 1);
                q.push({dist[v], v});
            }

            rep(x, -2, 2) {
                int nt = sqrt(d) + x; //出发时间
                if (nt < t) continue;
                if (nt + c + d / (nt + 1) < dist[v]) {
                    dist[v] = nt + c + d / (nt + 1);
                    q.push({dist[v], v});
                }
            }
        }
    }
    print(dist[n] == inf ? -1 : dist[n]);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    #ifdef PRE
        pre();
    #endif
    #ifdef MULTI_CASES
        int t; cin >> t;
        while (t--) solve();
    #else
        solve();
    #endif
    return 0;
}