#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define f first
#define s second
#define all(vec) begin(vec), end(vec)
#define pf push_front
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define mk make_pair
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;


const int N = 1e5+3;
struct ed{
    int i; ll c, d, x;
};
vector<ed> adj[N];
int n, m;
ll check(ll t){
    vector<ll> dis(n+1, 1e18);
    dis[1] = t;
    priority_queue<pli, vector<pli>, greater<pli>> q;
    q.push(mk(dis[1], 1));
    while(!q.empty()){
        int v = q.top().s;
        if(dis[v] != q.top().f){q.pop(); continue;}
        q.pop();
        for(auto& e : adj[v]){
            ll x = e.x;
            if(dis[v] >= x)x = 0;
            else x = x-dis[v];
            if(dis[v]+e.c+e.d/(dis[v]+x+1)+x < dis[e.i]){
                dis[e.i] = dis[v]+e.c+e.d/(dis[v]+x+1)+x;
                q.push(mk(dis[e.i], e.i));
            }
        }
    }
    return dis[n];
}
void solve(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int a, b; ll c, d;
        cin >> a >> b >> c >> d;
        ll l = 0, r = d, mid;
        while(l < r){
            mid = (l+r)/2;
            double x = (double)d/(mid+1)+mid;
            double y = (double)d/(mid+2)+mid+1;
            if(x < y){
                r = mid;
            }else{
                l = mid+1;
            }
        }
        adj[a].pb(ed{b, c, d, l});
        adj[b].pb(ed{a, c, d, l});
    }
    ll ans = check(0);
    cout << (ans == 1e18 ? -1 : ans) << '\n';
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    freopen("input.in", "r", stdin);
//    freopen("output.out", "w", stdout);
    int tc = 1;
//    cin >> tc;
    while(tc--){
        solve();
    }
}

#include <bits/stdc++.h>
 
using namespace std; 
 
#define int long long 
 
template <typename T> 
void print_vec(const vector<T>& v, bool newline = true) {
    for (int i = 0; i < v.size(); ++i) {
        cout << v[i] << " ";
    }
    if (newline) {
        cout << "\n";
    }
}
 
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
 
const int maxn = (int)2e5+105;
const int mod = (int)998244353 ; 
 
#define sz(x) ((int)(x.size()))
 
#define pb push_back
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repr(i,a,b) for (int i = (a); i >= (b); i--)
 
using vi = vector<int>;
 
int fact_setup=0; int * fact; 
 
int ex (int a, int b){
    if(b==0)return 1; int e = ex(a,b/2); e=(1ll*e*e)%mod; if(b&1)e=(1ll*e*a)%mod; return e;
}
int inv (int a){
    return ex(a, mod - 2); 
}
int choose (int a, int b){
    if(!fact_setup){
        fact_setup=1; 
        fact = new int [maxn]; 
        fact[0]=1; rep (i,1,maxn-1) fact[i]=(i*fact[i-1])%mod; 
    }
    if(a<b)return 0; 
    int num = fact[a]; 
    int denom = (fact[b] * fact[a - b]) % mod; 
    return (num * inv(denom)) % mod; 
}
 
#define pii pair <int, int> 
#define pvi pair <vector <int>, int> 
 
#define pai array <int,2>
#define pdi array <double, 2> 
#define pdt array <double, 3>
 
#define pti array <int,3>
#define pfi array <int,4>
 
#define all(v) v.begin(), v.end()

int n, m; 
vector<pti>ed[maxn]; 

int vis[maxn]; 
int dist[maxn]; 

main(){

	memset(dist,-1,sizeof(dist));  
	
    ios_base::sync_with_stdio(0);
	cin >> n >> m ;
	rep (i,1,m){
		int a,b,c,d;cin>>a>>b>>c>>d; 
		ed[a].pb({b,c,d}); 
		ed[b].pb({a,c,d}); 
	}
	
	priority_queue <pai,vector<pai>, greater<pai> > pq; 
	pq.push({0, 1});
	while(sz(pq)){
		pai tp = pq.top(); pq.pop(); 
		int node = tp[1], dis = tp[0]; 
		if (vis[node]) continue; 
		vis[node] = 1; 
		dist[node] = dis; 
		for (pti i : ed[node]){
			int nod = i[0], c = i[1], d = i[2]; 
			int new_dis = dis; 
			int kc  = (int)sqrt(d); if (kc*kc!=d) kc++; 
			
			kc--; 
			new_dis = max(new_dis,  kc); 
			pq.push({new_dis + c + (d/(new_dis+1)), nod}); 
		}
	}
	cout << dist[n]; 
    return 0; 
}