#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long int
#define ve vector<ll>
#define ve_pa vector<pair<ll,ll> >
#define pb push_back
#define mod (ll)998244353
#define INF (ll)1e18+7
#define ld long double 
#define pll pair<ll,ll>
#define fi first
#define se second
#define mll map<ll,ll>
#define m_ve map<ll,ve>
#define min3(x,y,z) min(x,min(y,z))
#define max3(x,y,z) max(x,max(y,z))
#define W(x) while(x--)
#define ld long double
#define all(x) x.begin(),x.end()
#define popcount(x) __builtin_popcountll(x)
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
//int dx[]={0,1,-1,0,0,1,-1,-1,1},dy[]={0,0,0,1,-1,1,-1,1,-1};	
const int N=100005;
vector<pair<ll,pll> >g[N];
ll dist[N],v[N];
ll n,m;
ll solve()
{
	for(int i=0;i<=n;i++)
	{
	dist[i]=INF;
	v[i]=0;
	}
	set<pll>s;
	s.insert({0,1});
	dist[1]=0;
	while(s.size())
	{
		pll x=*s.begin();
		s.erase(s.begin());
		if(v[x.se])
		continue;
		v[x.se]=1;
		for(auto x1:g[x.se])
		{
			ll ch=x1.fi;
			ll c=x1.se.fi;
			ll d=x1.se.se;
			ll w=dist[x.se];
				for(ll t=sqrt(d)-2;t<=sqrt(d)+2;t++)
				{
					ll nw=max(w,t);
					if(nw+c+d/(nw+1)<dist[ch])
					{
						dist[ch]=nw+c+d/(nw+1);
						s.insert({dist[ch],ch});
					}
				}
			
		}
	}
	return dist[n];
}
 
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); 
cout.tie(NULL);
int t;//cin>>t;
t=1;
while(t--)
{
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		ll u,v,c,d;cin>>u>>v>>c>>d;
		g[u].pb({v,{c,d}});
		g[v].pb({u,{c,d}});
	}	
	ll ans=INF;
	ans=solve();
	if(ans==INF)
	ans=-1;
	cout<<ans<<"\n";
} 
 
 
 
}
// E - Rush Hour 2
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define vec vector
using vl = vec<ll>;
#define rep(i,e) for(int i=0;i<(e);++i)
using PR = pair<ll,int>;

// 本問用に修正
// dijkstra O(|E|log|V|)
int V;
vec<tuple<int,int,int,int>> E;
vec<vec<int>> G;
ll INF = 1e18;

vl dijkstra(int s){
	vl dist(V, INF);
	dist[s] = 0;
	priority_queue<PR, vec<PR>, greater<PR>> pq;
	pq.push({0, s});
	while(pq.size()){
		auto[t, v] = pq.top(); pq.pop();
		if(dist[v] < t) continue;
		for(int&i:G[v]){
			auto&[a, b, c, d] = E[i];
			int u = a==v? b:a;
			ll k = round(sqrt(d)) - 1;
			if(k <= t) k = t;
			ll nt = k + c + d / (k+1);
			if(dist[u] <= nt) continue;
			dist[u] = nt;
			pq.push({nt, u});
		}
	}
	return dist;
}

int main(){
	int m; cin>>V>>m;
	G.resize(V);
	rep(i, m){
		int a, b, c, d; cin>>a>>b>>c>>d; --a, --b;
		E.emplace_back(a, b, c, d);
		G[a].push_back(i), G[b].push_back(i);
	}
	ll ans = dijkstra(0)[V-1];
	if(ans == INF) ans = -1;
	cout<< ans <<endl;
}
