#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Edge{
  int v,c,d;
  inline ll arrive(ll t){
    return t+c+ll(d)/(t+1);
  }
  inline ll tmin(ll t0){
    return arrive(max(t0,ll(round(sqrt(d)))-1));
  }
};

int main(){
  int n,m;
  cin>>n>>m;
  vector<vector<Edge>> adj(n);
  for(int i=0;i<m;i++){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    a--;
    b--;
    adj[a].push_back({b,c,d});
    adj[b].push_back({a,c,d});
  }
  priority_queue<pair<ll,int>> pq;
  vector<ll> dist(n,-1);
  pq.push({0,0});
  while(!pq.empty()){
    int u=pq.top().second;
    ll t0=-pq.top().first;
    pq.pop();
    if(dist[u]!=-1)continue;
    dist[u]=t0;
    for(auto &e:adj[u])
      if(dist[e.v]==-1)
        pq.push({-e.tmin(t0),e.v});
  }
  cout<<dist[n-1]<<endl;
}
//wtrl,everybody hangbeat me
#include<bits/stdc++.h>
/*#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>*/
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef pair<ll,ll> pll;
/*=====================================================================*/
#define pb push_back
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(s) (s).begin(),(s).end()
#define repd(i,n) for(int i=n-1;i>=0;i--)
#define forn(i,p,n) for(int i=p;i<=n;i++)
#define ford(i,p,n) for(int i=n;i>=p;i--)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();++i)
#define INF 1e9
#define PI acos(-1)
/*=====================================================================*/
string int_to_string(ll n)
{
	string s="";
	while(n)
	{
		ll now=n%10;
		s+=now+'0';
		n/=10;
	}
	reverse(s.begin(),s.end());
	return s;
}
ll string_to_int(string s)
{
	ll n=0;
	rep(i,s.size())
	{
		n*=10;
		n+=s[i]-'0';
	}
	return n;
}
/*======================================================================*/
const int dx[]={-1,0,1,0};
const int dy[]={0,-1,0,1};
const int month[2][12]={{31,28,31,30,31,30,31,31,30,31,30,31},{31,29,31,30,31,30,31,31,30,31,30,31}};
struct node
{
	ll to;
	ll c;
	ll d;
};
vector<node> v[100010];
ll dist[100010];
bool use[100010];
inline ll calc(ll down,ll up)
{
	ll res=max(down,(ll)sqrt((ll)up));
	while(up/(res+1)>up/(res+2))
	{
		res++;
	}	
	return res-down+up/(res+1);
}
void dijkstra(ll now)
{
	priority_queue<pll> pq;
	pq.push(pll((ll)0,(ll)now));
	dist[now]=(ll)0;
	while(!pq.empty())
	{
		pll now=pq.top();
		pq.pop();
		ll nd=now.second;
		if(use[nd]==1)
		{
			continue;
		}
		use[nd]=1;
		rep(i,v[nd].size())
		{
			ll cost=v[nd][i].c+calc(dist[nd],v[nd][i].d); 
			//cout<<cnt<<endl;
			if(dist[nd]+cost>=dist[v[nd][i].to])
			{
				continue;
			}
			dist[v[nd][i].to]=cost+dist[nd];
			pq.push(pll(-dist[v[nd][i].to],(ll)v[nd][i].to));
		}
	}
}
void solve()
{
	int n,m;
	cin>>n>>m;
	rep(i,m)
	{
		ll a,b,c,d;
		scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
		v[a].pb({b,c,d});
		v[b].pb({a,c,d});
	}
	forn(i,1,n)
	{
		dist[i]=1e18;
	}
	dijkstra(1);
	printf("%lld",dist[n]==1e18?-1:dist[n]);
}
/*======================================================================*/
int main()
{
   // std::ios::sync_with_stdio(false);
  /*
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
  */
  /*====================================================================*/
  int t=1;
  //cin>>t;
  while(t--)
  {
  	solve();
  }
  return 0;
}
/*
注意数组越界，vector长度为0的时候循环会RE
注意输入顺序
注意循环时int*int爆ll
注意答案存爆ll
*/

