//g++  7.4.0

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 100005
ll C[MAXN];
ll D[MAXN];
vector<pair<ll,ll>> adj[MAXN];
ll dis[MAXN];

ll getDis(ll t, ll c, ll d)
{
    return(t + c + d/(t + 1LL));
}

void dijkstra(ll source)
{
    set<pair<ll,ll>> s;
    s.insert({dis[source], source});
    
    while(!s.empty())
    {
        pair<ll,ll> p = *s.begin();
        s.erase(p);
        ll u = p.second;
        //cout<<u<<endl;
        
        for(auto it: adj[u])
        {
            ll v = it.first;
            ll index = it.second;
            ll c = C[index];
            ll d = D[index];
            
            ll wait = max(0LL, (ll)sqrt(d) - dis[u]);
            ll ans = LLONG_MAX;
            for(ll i=0;i<=3;++i)
            {
                ll w = max(0LL, wait + i);
                ans = min(ans, getDis(w + dis[u], c, d));
                w = max(0LL, wait - i);
                ans = min(ans, getDis(w + dis[u], c, d));
            }
            
            //cout<<u<<" "<<v<<" "<<ans<<endl;
            
            if(dis[v] > ans)
            {
                s.erase({dis[v], v});
                dis[v] = ans;
                s.insert({dis[v], v});
            }
        }
    }
}

//Shit Man: There can be multiple edges as well
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll N,M; cin>>N>>M;
    
    for(ll i=1;i<=N;++i)
        dis[i] = LLONG_MAX;
    
    for(ll i=0;i<M;++i)
    {
        ll u,v; cin>>u>>v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
        cin>>C[i];
        cin>>D[i];
    }
    
    dis[1] = 0;
    dijkstra(1);
    
    if(dis[N] == LLONG_MAX)
        cout<<-1<<endl;
    else
        cout<<dis[N]<<endl;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd_(ll a,ll b){if(a%b==0)return b;return gcd_(b,a%b);}
ll lcm_(ll a,ll b){ll c=gcd_(a,b);return ((a/c)*b);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=ll(1e18)+ll(7);
const ll MOD=1000000007LL;
#define out(a) cout<<fixed<<setprecision((a))
//tie(a,b,c) = make_tuple(10,9,87);
#define pop_(a) __builtin_popcount((a))
ll keta(ll a){ll r=0;while(a){a/=10;r++;}return r;}
#define num_l(a,v) POSL(a,v) //v未満の要素数
#define num_eql(a,v) POSU(a,v) //v以下の要素数
#define num_h(a,v) (a.size() - POSU(a,v)) //vより大きい要素数
#define num_eqh(a,v) (a.size() - POSL(a,v)) //v以上の要素数
// static_cast< long long ll >


int main(){
	int N,M;
	cin >> N >> M;

	vector<ll> G[N+1];
	vector<ll> A(M),B(M),C(M),D(M);


	FOR(i,0,M){
		cin >> A[i] >> B[i] >> C[i] >> D[i];
		G[A[i]].push_back(i);
		G[B[i]].push_back(i);
	}


	priority_queue<P, vector<P>, greater<P> > Q; //小さいものから出る

	Q.push({0,1});//{Time,vart}
	vector<int> did(N+1,0);
	vector<ll> T(N+1,INF);
	T[1] = 0;

	while(Q.size()){
		int u = Q.top().second;
		Q.pop();
		if(did[u])continue;
		did[u] = true;
		FOR(ind,0,G[u].size()){
			int v = B[G[u][ind]];
			if(v==u) v = A[G[u][ind]];
			if(did[v])continue;
			if(u==v)continue;

			ll t = sqrt(D[G[u][ind]]);
			ll at = INF;
			FOR(j,max(t-100,T[u]),max(t+100,T[u])+1){//出る時刻
				at = min(at, j + D[G[u][ind]]/(j+1) + C[G[u][ind]]);
			}
			//cout << at << " atat" << endl;
			if(T[v] > at){
				T[v] = at;
				Q.push({at,v});
			}

		}
	}

	if(T[N] == INF)T[N] = -1;
	cout << T[N] << endl;
	//FOR(i,0,N+1) cout << T[i] << " ";
}
