#include <bits/stdc++.h>

using namespace std;

#define MP make_pair
#define PB push_back
#define REP(i, L, R) for (int i = L; i < (R); ++i)
#define SZ(x) (int)x.size()

using ll = long long;
using ld = long double;
using P = pair<ll, int>;

template <typename T>
bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

ll ternary_search(double lo, double hi, ll c, ll d)
{
    double eps = 1e-3;
    while (hi - lo > eps)
    {
        double m1 = lo + (hi - lo) / 3;
        double m2 = hi - (hi - lo) / 3;
        double f1 = m1 + c + d / (m1 + 1.);
        double f2 = m2 + c + d / (m2 + 1.);
        if (f1 < f2)
        {
            hi = m2;
        }
        else
        {
            lo = m1;
        }
    }

    return (ll)floor(lo);
}

struct e
{
    int to;
    ll c, d;
    e(int to, ll c, ll d) : to(to), c(c), d(d) {}

    ll f(ll t)
    {
        return t + c + d / (t + 1);
    }

    ll get(ll t)
    {
        if (t >= d)
        {
            return f(t); // always = t+c
        }

        ll lo = ternary_search((double)t, (double)(d + 1.), c, d);
        return min(f(lo), f(lo + 1));
        /*
        // find t' such that f(t') is minimized.
        ll lo = t, hi = d + 1;
        while (lo + 1 < hi)
        {
            ll mid = (hi - lo) / 2 + lo;
            if (mid * mid + mid < d)
            {
                lo = mid;
            }
            else
            {
                hi = mid;
            }
        }

        return min(f(lo), f(lo + 1));
*/
    }
};

const int MAXN = 1e5 + 1;
const ll INF = 1e18;
ll d[MAXN];

void dijkstra(int s, int n, const vector<vector<e>> &g)
{
    priority_queue<P, vector<P>, greater<P>> que;
    fill(d, d + n, INF);
    d[s] = 0;
    que.push(MP(0, s));

    while (!que.empty())
    {
        auto [dv, v] = que.top();
        que.pop();
        if (dv > d[v])
        {
            continue;
        }
        for (auto e : g[v])
        {
            ll nextt = e.get(d[v]);
            if (nextt < d[e.to])
            {
                d[e.to] = nextt;
                que.push(MP(d[e.to], e.to));
            }
        }
    }
}

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<vector<e>> g(n, vector<e>());

    REP(i, 0, m)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        g[a - 1].emplace_back(b - 1, c, d);
        g[b - 1].emplace_back(a - 1, c, d);
    }
    dijkstra(0, n, g);
    cout << (d[n - 1] == INF ? -1 : d[n - 1]) << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    while (T--)
    {
        solve();
    }
    return 0;
}

//in dp prefix suffix sum helps..
//map adds a logn factor.Try using 2d array.
#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<stack>
#include <chrono>
#include <random>
#include <iterator>
#include <map>
#include<list>
#include<sstream>
#include <algorithm>
#include <fstream>
#include<unordered_map>
#include<set>
#include<queue>
#define int  long long
#define double long double
#define pb   push_back
#define mp   make_pair
#define pii  pair<int,int>
#define pip pair<int,pii>
#define vip vector<pip>
#define vi vector<int>
#define vs vector<string>
#define vd vector<double>
#define mii  map<pii, int>
#define qu queue<int>
#define set set<pii>
#define multiset multiset<int>
#define rep(i, a, b) for(int i=a;i<b;i++)
#define rep1(i, b, a) for(int i=b;i>=a;i--)
#define viv vector<viv>
#define stack stack<int>
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define it iterator
#define pq priority_queue<int>
#define pq1 priority_queue <pii, vector<pii>, greater<pii> >
#define mem(x, y) memset(x, (int)y, sizeof(x))
#define ps(x,y) fixed<<setprecision(y)<<x
// author :: Anurag Anand.
using namespace std;
int z=  1e9+7;
//int z= 998244353;
int gcd(int a, int b){
    if(a==0)return b;
    if(b==0)return a;
    return gcd(b, a%b);
}
int power(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=(res*a)%z, b--;
		a=(a*a)%z;
		b=b>>1;
	}
	return res;
}
vi sv;
int fact[1000001];
int ncr(int n, int r){
	int p=fact[n];
	p*=power(fact[r], z-2);
	p%=z;
	p*=power(fact[n-r], z-2);
	p%=z;
	return p;
}

// vi seg;
// void arrange(int i, int v, int x, int lx, int rx){
// 	if(rx-lx==1){
// 		seg[x]=v;
// 		return;
// 	}
// 	int mid=(lx+rx)/2;
// 	if(i<mid) arrange(i, v, 2*x+1, lx, mid);
// 	else arrange(i, v, 2*x+2, mid, rx);
// 	seg[x]= min(seg[2*x+1], seg[2*x+2]);
// }

// int calc(int l, int r, int x, int lx, int rx){
// 	if(lx>=r||l>=rx) return 1e9;
// 	if(lx>=l&&rx<=r) return seg[x];
// 	int mid=(lx+rx)/2;
// 	int k1=calc(l, r, 2*x+1, lx, mid), k2=calc(l, r, 2*x+2, mid, rx);
// 	return min(k1, k2);
// }
vi pp;
int dist[100001];
vip v1[100001];
mii mc, md;
void dijkstra(int root){
	int a, d;
	dist[root]=0;
	set s;
	s.insert(mp(0, root));
	while(!s.empty()){
		a= (*s.begin()).se;
		s.erase(s.begin());
		for(int i=0;i<v1[a].size();i++){
			int y=v1[a][i].fi;
			int c=v1[a][i].se.fi, d=v1[a][i].se.se;
			int p2=ceil(sqrt(d)-1);
			p2= max(p2, dist[a]);
			int t1=p2+c+d/(p2+1);
			if(t1<dist[y]){
				s.erase(mp(dist[y], y));
				dist[y]=t1;
				s.insert(mp(dist[y], y));
			}
		}
	}
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cout.tie(NULL);
	// freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
	pp.assign(1000001, 0);
	for(int i=2;i<1000;i++){
		if(!pp[i]){
			for(int j=i*i;j<=1000000;j+=i){
				pp[j]=1;
			}
		}
	}
	fact[0]=1;
	rep(i,1,1000001) fact[i]=i*fact[i-1], fact[i]%=z;
	for(int i=2;i<=1000000;i++) if(!pp[i]) sv.pb(i);
	int t;
	t=1;
	//cin>>t;
	while(t--){
		int n, m, x, y, c, d;
		cin>>n>>m;
		rep(i,0,m){
			cin>>x>>y>>c>>d;
			v1[x].pb(mp(y, mp(c,d)));
			v1[y].pb(mp(x, mp(c,d)));
		}
		rep(i,1,n+1) dist[i]=1e16;
		dijkstra(1);
		if(dist[n]==1e16) dist[n]=-1;
		cout<<dist[n]<<"\n";
	}
}