/**
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡀⠀⠀⠀⠀⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⡖⠁⠀⠀⠀⠀⠀⠀⠈⢲⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣼⡏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⣧⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣸⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣿⣇⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣿⣿⡇⠀⢀⣀⣤⣤⣤⣤⣀⡀⠀⢸⣿⣿⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⢻⣿⣿⣔⢿⡿⠟⠛⠛⠻⢿⡿⣢⣿⣿⡟⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⣀⣤⣶⣾⣿⣿⣿⣷⣤⣀⡀⢀⣀⣤⣾⣿⣿⣿⣷⣶⣤⡀⠀⠀⠀⠀
⠀⠀⢠⣾⣿⡿⠿⠿⠿⣿⣿⣿⣿⡿⠏⠻⢿⣿⣿⣿⣿⠿⠿⠿⢿⣿⣷⡀⠀⠀
⠀⢠⡿⠋⠁⠀⠀⢸⣿⡇⠉⠻⣿⠇⠀⠀⠸⣿⡿⠋⢰⣿⡇⠀⠀⠈⠙⢿⡄⠀
⠀⡿⠁⠀⠀⠀⠀⠘⣿⣷⡀⠀⠰⣿⣶⣶⣿⡎⠀⢀⣾⣿⠇⠀⠀⠀⠀⠈⢿⠀
⠀⡇⠀⠀⠀⠀⠀⠀⠹⣿⣷⣄⠀⣿⣿⣿⣿⠀⣠⣾⣿⠏⠀⠀⠀⠀⠀⠀⢸⠀
⠀⠁⠀⠀⠀⠀⠀⠀⠀⠈⠻⢿⢇⣿⣿⣿⣿⡸⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⠈⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣼⣿⣿⣿⣿⣧⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠐⢤⣀⣀⢀⣀⣠⣴⣿⣿⠿⠋⠙⠿⣿⣿⣦⣄⣀⠀⠀⣀⡠⠂⠀⠀⠀
⠀⠀⠀⠀⠀⠈⠉⠛⠛⠛⠛⠉⠀⠀⠀⠀⠀⠈⠉⠛⠛⠛⠛⠋⠁⠀⠀
**/
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define nl cout<<"\n";
#define ll long long int
#define ld double
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define F(i,a,b) for(i=a;i<b;i++)
//#include <ext/pb_ds/assoc_container.hpp> // policy based data structure header files
//#include <ext/pb_ds/tree_policy.hpp> // policy based data structure header files
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
//using namespace __gnu_pbds; // for pbds
//#define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> // have functions like order_of_key, find_by_order
const double PI = 3.14159265358979323846264338327950288419716939937510582097494459230781641;
const ll M=1e18;
const ll MAXN=100200;
ll i,j,mask;
void solve()
{
    ll n, m;
    cin>>n>>m;
    vector<vector<pair<ll, pair<ll,ll> > > > v(n+1);
    while(m--) {
        ll a, b, c, d;
        cin>>a>>b>>c>>d;
        v[a].pb({b, {c, d} });
        v[b].pb({a, {c, d} });
    }
    priority_queue<pair<ll,ll>, vector<pair<ll,ll> >, greater<pair<ll,ll> > > pq;
    pq.push({0, 1});
    vector<ll> dist(n+1, M), vis(n+1);
    dist[1]=0;
    while(!pq.empty()) {
        ll t=pq.top().fi;
        ll node=pq.top().se;
        pq.pop();
        if(vis[node])
            continue;
        vis[node]=1;
        for(auto x:v[node]) {
            ll to=x.fi, c=x.se.fi, d=x.se.se;
            ll k;
            ll g=sqrt(d);
            ll change=M;
            F(k,max((ll)0, g-2), g+3) {
                ll val=max(k, t);
                change=min(change, val+c+d/(val+1));
            }
            if(change<dist[to]) {
                dist[to]=change;
                pq.push({change, to});
            }
        }
    }
    if(dist[n]==M) {
        cout<<-1;
    } else {
        cout<<dist[n];
    }
}
int main()
{
    IOS
    /*#ifndef ONLINE_JUDGE
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
    #endif // ONLINE_JUDGE*/
    ll t,test=1;
    // cin>>test;
    F(t,1,test+1) {
        //cout<<"Case #"<<t<<": ";
        solve();
        nl
    }
    return 0;
}

#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <climits>

#define rep(i, n) for(int i = 0; i < n; i++)
#define per(i, n) for(int i = n - 1; i >= 0; i--)
using ll = long long;
#define vi vector<int>
#define vvi vector<vi>
#define vl vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define mod 1000000007
using namespace std;
template<class T, class U>
T &chmax(T &a, const U &b){ if(a < b) a = b; return a; }
template<class T, class U>
T &chmin(T &a, const U &b){ if(a > b) a = b; return a; }
ll search(int d){
  double left = 0, right = 2e14;
  rep(_, 100){
    double l = (left*2 + right) / 3;
    double r = (left + right*2) / 3;
    double f1 = d/(l + 1) + l;
    double f2 = d/(r + 1) + r;
    if(f1 > f2) left = l;
    else right = r;
  }
  return ceil(left);
}
int main(){
  int n,m;
  cin >> n >> m;
  vector<vector<tuple<int,ll,ll>>> root(n);
  rep(i, m){
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    a--; b--;
    root[a].push_back({b, c, d});
    root[b].push_back({a, c, d});
  }
  priority_queue<pll, vector<pll>, greater<pll>> que;
  que.push({0, 0});
  vl checked(n, -1);
  checked[0] = 0;
  while(!que.empty()){
    ll pos, score;
    tie(score, pos) = que.top();
    que.pop();
    if(checked[pos] != -1 && checked[pos] < score) continue;
    for(auto x : root[pos]){
      ll s = search(get<2>(x));
      chmax(s, score);
      ll v = s + get<1>(x) + get<2>(x) / (s + 1);
      //cout << s << " " << v << "\n";
      if(checked[get<0>(x)] != -1 && checked[get<0>(x)] <= v) continue;
      checked[get<0>(x)] = v;
      que.push({v, get<0>(x)});
    }
  }
  //rep(i, n) cout << checked[i] << " ";
  cout << checked[n - 1] << "\n";
}