#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL << 60;

struct Edge {
    int to;
    pair<ll,ll>w;
    Edge(int to, pair<ll,ll> w) : to(to), w(w) {}
};

using Graph = vector<vector<Edge>>;

template<class T> bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    else return false;
}

int main() {
    int N, M, s;
    cin >> N >> M;
	s=0;
 
    Graph G(N);
    for (int i = 0; i < M; ++i) {
      int a, b;cin>>a>>b;a--;b--;
      ll w,d;
      cin>>w>>d;
      G[a].push_back(Edge(b, {w,d}));
      G[b].push_back(Edge(a,{w,d}));
    }

    // ダイクストラ法
    vector<long long> dist(N, INF);
    dist[s] = 0;

    // (d[v], v) のペアを要素としたヒープを作る
    priority_queue<pair<long long, int>,
                   vector<pair<long long, int>>,
                   greater<pair<long long, int>>> que;
    que.push(make_pair(dist[s], s));

    // ダイクストラ法の反復を開始
        while (!que.empty()) {
        // v: 使用済みでない頂点のうち d[v] が最小の頂点
        // d: v に対するキー値
        int v = que.top().second;
        long long d = que.top().first;
        que.pop();

        // d > dist[v] は，(d, v) がゴミであることを意味する
        if (d > dist[v]) continue; 
        // 頂点 v を始点とした各辺を緩和
        for (auto e : G[v]) {
          for(int t=(int)sqrt(e.w.second)-2;t<=(int)sqrt(e.w.second)+2;t++){
            if(t<0)continue;
          if(dist[v]<=t){
            if (chmin(dist[e.to], t + e.w.first+e.w.second/(t+1))) {
                // 更新があるならヒープに新たに挿入
                que.push(make_pair(dist[e.to], e.to)); 
              }
          }
          else{
            if (chmin(dist[e.to], dist[v] + e.w.first+e.w.second/(dist[v]+1))) {
                // 更新があるならヒープに新たに挿入
                que.push(make_pair(dist[e.to], e.to)); 
            }
          }
          }
        }
    }

    // 結果出力
    if (dist[N-1] < INF) cout << dist[N-1] << endl;
    else cout << -1 << endl;
}
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back               
#define mp make_pair         
#define nline "\n"
const ll M1=1e9+7;                                               
const ll M=998244353;                    
const ll N=100005;   
const ll INF_ADD=1e18;
const ll INF_MUL=1e13;                                    
#define f first                          
#define s second                             
#define pll pair<ll,ll>   
#ifndef ONLINE_JUDGE 
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);
#endif  
void _print(ll x){cerr<<x;}    
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";} 
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
ll optimal(ll x,ll t){
    ll sq=sqrt(x);
    set<ll> comp;
    comp.insert(t+x/(t+1));
    if(sq>t)   
        comp.insert(sq+x/(sq+1));
    sq++;    
    if(sq>t)  
        comp.insert(sq+x/(sq+1));
    sq++;
    if(sq>t)
        comp.insert(sq+x/(sq+1));
    sq=sqrt(x);
    sq--;
    if(sq>t)
        comp.insert(sq+x/(sq+1));
    sq--;
    if(sq>t)
        comp.insert(sq+x/(sq+1));
    ll best=*(comp.begin());
    return best;
}
void solve(){   
    ll n,m; cin>>n>>m;
    vector<vector<pll>> adj(n+2);
    vector<ll> ans(n+5,INF_ADD);
    priority_queue<pll> prefer;
    prefer.push({0,1});
    vector<vector<ll>> a(m+4,vector<ll>(5,0));
    ans[1]=0;
    for(ll i=1;i<=m;i++){
        for(ll j=1;j<=4;j++)
            cin>>a[i][j];
        adj[a[i][1]].pb({a[i][2],i});
        adj[a[i][2]].pb({a[i][1],i}); 
    }
    while(prefer.size()){
        auto it=prefer.top();
        prefer.pop();
        if(ans[it.s]!=-it.f)
            continue;
        ll node=it.s,instant=-it.f;
        for(auto chld:adj[node]){
            ll compare=(a[chld.s][3]+optimal(a[chld.s][4],instant));
            if(compare<ans[chld.f]){
                prefer.push({-compare,chld.f});
                ans[chld.f]=compare;
            }
        }
    }
    if(ans[n]!=INF_ADD)
        cout<<ans[n];
    else
        cout<<"-1";

}             
int main()                                             
{         
    ios_base::sync_with_stdio(false);                        
    cin.tie(NULL);                     
    #ifndef ONLINE_JUDGE          
    freopen("input.txt", "r", stdin);                                         
    freopen("output.txt", "w", stdout);  
    freopen("error.txt", "w", stderr);                        
    #endif    
    ll t=1;           
    //cin>>t;
    while(t--){
        solve();
    }
    /*
    Correct data type?
    Infinity?
    Base case?
    */
    cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
} 