#include <bits/stdc++.h>

typedef long long int ll;
typedef long double ld;
using namespace std;
#define P 1000000007
#define rep(i,n) for(i=0;i<n;++i)
#define re(i,a,n) for(i=a;i<=n;++i)
#define repr(i,a,n) for(i=a;i>=n;--i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define endl "\n"
#define ub(v,val) upper_bound(v.begin(),v.end(),val)
#define np(str) next_permutation(str.begin(),str.end())
#define lb(v,val) lower_bound(v.begin(),v.end(),val)
#define sortv(vec) sort(vec.begin(),vec.end())
#define rev(p) reverse(p.begin(),p.end());
#define mset(a,val) memset(a,val,sizeof(a));
#define at(s,pos) *(s.find_by_order(pos))
#define set_ind(s,val) s.order_of_key(val)
#define PI 3.14159265
/*#include <ext/pb_ds/assoc_container.hpp> // Common file  
#include <ext/pb_ds/tree_policy.hpp>  
#include <functional> // for less  
#include <iostream>  
// Important header files   
using namespace __gnu_pbds;  
using namespace std;  
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;*/


ll binpowmod(ll a, ll b, ll m) {
    a %= m;
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

int findMin(vector<int> arr, int n)
{
    // Calculate sum of all elements
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
 
    // Create an array to store results of subproblems
    bool dp[n+1][sum+1];
 
    // Initialize first column as true. 0 sum is possible
    // with all elements.
    for (int i = 0; i <= n; i++)
        dp[i][0] = true;
 
    // Initialize top row, except dp[0][0], as false. With
    // 0 elements, no other sum except 0 is possible
    for (int i = 1; i <= sum; i++)
        dp[0][i] = false;
 
    // Fill the partition table in bottom up manner
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=sum; j++)
        {
            // If i'th element is excluded
            dp[i][j] = dp[i-1][j];
 
            // If i'th element is included
            if (arr[i-1] <= j)
                dp[i][j] |= dp[i-1][j-arr[i-1]];
        }
    }
  
    // Initialize difference of two sums.
    int diff = sum;
     
    // Find the largest j such that dp[n][j]
    // is true where j loops from sum/2 t0 0
    for (int j=sum/2; j>=0; j--)
    {
        // Find the
        if (dp[n][j] == true)
        {
            diff = sum-j;
            break;
        }
    }
    return diff;
}

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
   ll t,i,j,f,e,x,y,mid,z,w,d,c,b,h,a,k,q,p;
   ll t1,t2,t3,ans=0,tc,t4,m,l,n ;
   cin >> n >> m;
   vector<vector<pair<ll,pair<ll,ll>>>> adj(n+1);
   rep(i,m)
   {
      cin >> x >> y >> a >> b ;
      adj[x].pb({y,{a,b}});
      adj[y].pb({x,{a,b}});
   }
   vector<ll> dist(n+1,1e18);
   dist[1]=0;
   set<pair<ll,ll>> s;
   s.insert({0,1});
   while(!s.empty())
   {
    auto u=*s.begin();
    s.erase(s.begin());
    for(auto v:adj[u.se])
    {
        ll x = ceil(sqrt(v.se.se));
        if(u.fi>=x) 
        {
          if(dist[v.fi]>u.fi+v.se.fi+(v.se.se)/(u.fi+1))
          {
            s.erase({dist[v.fi],v.fi});
            dist[v.fi]=u.fi+v.se.fi+(v.se.se)/(u.fi+1) ;
            s.insert({dist[v.fi],v.fi});

          }
        }
        else
        {
          t1=u.fi+v.se.fi+x-u.fi-1;
          //cout << t1 << endl ;
          t1+=(v.se.se)/x;
          //cout << t1 << endl ;
          if(dist[v.fi]>t1)
          {
            s.erase({dist[v.fi],v.fi});
            dist[v.fi]=t1 ;
            s.insert({dist[v.fi],v.fi});

          }
        }
    }
   }
   if(dist[n]==1e18) cout << -1 ;
   else cout << dist[n] ;


  return 0;
   
          
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mod 1000000007   

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

ll binpow(ll x,ll y)/* (x^y)%p in O(log y) */{ll res=1;while (y > 0){if(y&1)res=(res*x);y = y>>1;x=(x*x);}return res;}
ll binpowmod(ll x,ll y,ll p)/* (x^y)%p in O(log y) */{ll res=1;x=x%p;while (y > 0){if(y&1)res=(res*x)%p;y = y>>1;x=(x*x)%p;}return res;}
ll mod_inverse(ll n,ll p)/* Returns n^(-1) mod p */{return binpowmod(n,p-2,p);}
ll gcd(ll x,ll y)
{
    if(y==0)
        return x;
    return gcd(y,x%y);
}
bool comp_pairs_by_s(pair<ll,ll> &x ,pair<ll,ll> &y)
{
    return x.second<y.second;
}
bool isPowerOfTwo (ll x)  
{  
    /* First x in the below expression is for the case when x is 0 */
    return x && (!(x&(x-1)));  
}

class cmp      //comrootator for priority_queue 
{               //declaration: priority_queue<int,vector<int>,cmp>
public:         
    bool operator()(pair<ll,ll>& A, pair<ll,ll>& B)
    {
        // if(A.first == B.first)
        //     return A.second < B.second;
        return A.first > B.first;
    }
};

void swap(int &x,int &y){
    int temp=x;
    x=y;
    y=temp;
}
  
unsigned int onesComplement(unsigned int n) 
{ 
   // Find number of bits in the given integer 
   int number_of_bits = floor(log2(n))+1; 
  
   // XOR the given integer with poe(2,  
   // number_of_bits-1 and print the result  
   return ((1 << number_of_bits) - 1) ^ n; 
}

bool comp1(pair<int,int> x,pair<int,int> y)
{
    return x.second<y.second;
}

const int N = 1e5 + 10;
struct node {
	int to;
	int c;
	int d;
};
vector<node> g[N];
void solve(){   
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < m; ++i) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		g[a].push_back({b, c, d});
		g[b].push_back({a, c, d});
	}

	priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, cmp> pq;
	vector<ll> ans(n + 1, 1LL * 1000 * 1000 * 1000 * 1000 * 1000 * 10);
	ans[1] = 0;
	pq.push({0, 1});
	while(!pq.empty()) {
		auto e = pq.top();
		pq.pop();
		int from = e.second; ll cost = e.first;
		if(ans[from] < cost)
			continue;
		for(node to: g[from]) {
			ll min_cost = cost + 1LL * to.c + to.d / (cost + 1);
			int sqr = int(sqrt(to.d));
			for(int i = max(0, sqr - 3); i <= sqr + 3; ++i) {
				min_cost = min(min_cost,
				cost + i * 1LL + 1LL * to.c + to.d / (cost + i * 1LL + 1LL)
								);
			}
			if(ans[to.to] > min_cost) {
				ans[to.to] = min_cost;
				pq.push({min_cost, to.to});
			}
		}
	}

	if(ans[n] == 1LL * 1000 * 1000 * 1000 * 1000 * 1000 * 10) {
		cout << -1;
	}
	else
		cout << ans[n];
}   

int main()                   
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout << fixed << setprecision(15);
    // int t;
    // cin >> t;
    // while(t--){
    //     solve();
    // }
    solve();
  
}   