/////keep going!~!one day u will int get there
#include<bits/stdc++.h>
#define ll         	long long
#define pb        	push_back
#define ppb    	  	pop_back
#define pii         pair<ll int,ll  int>
#define vi   	  	vector<ll int>
#define YES  	  	cout<<"YES"<<endl;
#define NO   	  	cout<<"NO"<<endl;
#define all(a)    	(a).begin(),(a).end()
#define uniq(v)   	(v).erase(all int(v),(v).end())
#define rep(i,a,b)	 for(int i=a;i<b;i++)
#define repo(i,a,b) for(int i=a;i>=b;i--)
#define fi      first
#define se      second
#define endl    '\n'
const ll int maxn=1e5+10;
const ll int mod=1e9+7;
using namespace std;
//powerer function
long long int power(long long int a,long long int b)
{long long int res = 1;
        while(b>0){
                if(b%2==1) res = res * a;
                a = a*a;
                b = b/2;
        }
        return res;	
}
//modular inverse
 ll int po( ll int x, ll int y){ ll int res=1;x=x%mod;while(y>0){if(y&1)res=((res%mod)*(x%mod))%mod;y=y>>1;x=((x%mod)*(x%mod))%mod;}return res;}


int main()
{ 
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t=1;
  //cin>>t;
  while(t--)
  {  
    int n,me;
    cin>>n>>me;
    vector < pair < int,pair<ll int,ll int> > > adj[n+1];
    for(int i=0;i<me;i++)
    {
    	ll x,y,a,b;
    	cin>>x>>y>>a>>b;
    	adj[x].pb({y,{a,b}});
    	adj[y].pb({x,{a,b}});	
	}
	ll int t[n+1];
	for(int i=0;i<=n;i++)
	t[i]=1e17+1;
	t[1]=0;
	int v[n+1]={0};	
	multiset < pair<ll int,int> > m;
	m.insert({0,1});
	while(m.size()>0)
	{
		pair < ll int,int> p=*m.begin();
		m.erase(m.begin());
		int node=p.se;
		ll int ct=p.fi;
		v[node]=1;
		if(t[node]<ct)
		continue;
		for(int i=0;i<adj[node].size();i++)
		{    int child=adj[node][i].fi;
		      ll int c=adj[node][i].se.fi,d=adj[node][i].se.se;
		      ll int val=1e17+1;
		      ll int sq=sqrt(d);
	          if(t[node]>sq+1)
	          val=t[node]+c+d/(t[node]+1);
	           else
	          for(int ti=max(t[node],sq-1);ti<=sq+1;ti++)
	          val=min(val,ti+c+d/(ti+1));
			if(!v[child]&&t[child]>val)
			{ 
				t[child]=val;
				m.insert({val,child});
			}	
		}
			
	}
	if(t[n]==1e17+1)
	cout<<"-1"<<endl;
	else
	cout<<t[n]<<endl;
  
  }
}

#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
#include <cstdint>
#include <string>
#include <sstream>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
#define rep(i,n) for (int i = 0; i < (n); ++i)
typedef long long ll;
using P=pair<ll,ll>;
const ll INF=1e18;
const int mod=1e9+7;

struct edge{
  int to;
  ll c,d;
  edge(int to,ll c,ll d):to(to),c(c),d(d){}
};
using Graph=vector<vector<edge>>;

void solve(){
  int n,m;
  cin>>n>>m;
  Graph G(n);
  rep(i,m){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    a--;b--;
    G[a].emplace_back(b,c,d);
    G[b].emplace_back(a,c,d);
  }

  vector<ll>dist(n,INF);
  dist[0]=0;
  priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>q;
  q.push({dist[0],0});
  while(!q.empty()){
    int v=q.top().second;
    ll tm=q.top().first;
    q.pop();
    if(tm>dist[v]){continue;}
    for(auto e:G[v]){
      ll t=max(0ll,(ll)(sqrt(e.d)-1-tm));
      ll t2=max(0ll,(ll)(sqrt(e.d)-tm));
      ll add=min(t+e.c+e.d/(tm+t+1),t2+e.c+e.d/(tm+t2+1));
      if(chmin(dist[e.to],tm+add)){q.push({dist[e.to],e.to});}
    }
  }
  //rep(i,n){cout<<dist[i]<<endl;}
  ll ans=dist[n-1];
  if(ans==INF){ans=-1;}
  cout<<ans<<endl;
}
 
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  solve();
}