//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 fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pb push_back
#define nl cout<<"\n"
#define all(x) x.begin(),x.end()

template<class C> void min_self( C &a, C b ){ a = min(a,b); }
template<class C> void max_self( C &a, C b ){ a = max(a,b); }

const ll MOD = 1000000007;
// const ll MOD = 998244353;
template<class T1, class T2> void add( T1 &x, T2 y, ll m = MOD ){ x += y; if( x >= m ) x -= m; }
template<class T1, class T2> void sub( T1 &x, T2 y, ll m = MOD ){ x -= y; if( x < 0 ) x += m; }
ll mod( ll n, ll m=MOD ){ n%=m;if(n<0)n+=m;return n; }

const int MAXN = 1e5+5;
const int LOGN = 21;
const ll INF = 1e16;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

vector<array<ll,3>> gr[MAXN];
ll dist[MAXN];

void dijkstra(int start)
{
	dist[start] = 0;
	priority_queue<array<ll,2>> pq;

	pq.push({0,start});

	auto travel = [&]( ll c, ll d, ll t )
	{
		return c + ( d / (t+1) );
	};

	while( !pq.empty() )
	{
		ll time = -pq.top()[0];
		int node = pq.top()[1];
		pq.pop();

		if( dist[node] != time )
			continue;

		for( auto it : gr[node] )
		{
			int nxt = it[0];
			ll c = it[1];
			ll d = it[2];
			ll sq = sqrt(d) - time - 1;

			ll best = INF;
			ll mn = max(time, sq-5);
			for(ll del=mn;del<=mn+10;del++)
				best = min( best, (del-time) + travel(c,d,del) );

			if( dist[node] + best < dist[nxt] )
			{
				dist[nxt] = dist[node] + best;
				pq.push({-dist[nxt], nxt});
			}
		}
	}
}

void solve()
{
	int n,m;
	cin>>n>>m;

	for(int i=1;i<=n;i++)
		dist[i] = INF;

	for(int i=0;i<m;i++)
	{
		int u,v,c,d;
		cin>>u>>v>>c>>d;
		gr[u].pb({v,c,d});
		gr[v].pb({u,c,d});
	}
	dijkstra(1);

	ll ans = dist[n];
	if( ans == INF )
		ans = -1;
	cout<<ans,nl;
}

int main()
{
	#ifdef gupta_samarth
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif
	fastio();

	int t = 1;
	// cin>>t;
	for(int test=1;test<=t;test++)
	{
		// cout<<"Case #"<<test<<": ";
		solve();
	}

	cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
	return 0;
}