#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ordered_set     tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
// find_by_order(k):    It returns to an iterator to the kth element (counting from zero) in the set
// order_of_key(k) :    It returns to the number of items that are strictly smaller than our item k
#define fast            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb              push_back
#define f               first
#define s               second
#define F(i,a,b)        for(i=a;i<b;i++)
#define nl              "\n"
#define sp              " " 
#define all(c)          (c).begin(),(c).end()
#define rev(i,b,a)      for(int i=b;i>=a;i--)
#define iota            cout<<-1<<nl
#define cty             cout<<"YES"<<nl
#define ctn             cout<<"NO"<<nl
#define lmax            LLONG_MAX
#define lmin            LLONG_MIN
#define sz(v)           (v).size()
#define deci(n)         fixed<<setprecision(n)
#define c(x)            cout<<(x)
#define csp(x)          cout<<(x)<<" "
#define c1(x)           cout<<(x)<<nl
#define c2(x,y)         cout<<(x)<<" "<<(y)<<nl
#define c3(x,y,z)       cout<<(x)<<" "<<(y)<<" "<<(z)<<nl
#define c4(a,b,c,d)     cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<nl
#define c5(a,b,c,d,e)   cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<" "<<(e)<<nl
#define c6(a,b,c,d,e,f) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<" "<<(e)<<" "<<(f)<<nl
typedef long double     ld;
typedef long long       ll;
typedef vector<ll>      vll;
typedef pair<ll,ll>     pll;
typedef vector<pll>     vpll;
const int mod=998244353;
const int mod1=1000000007;
const double pi=3.14159265358979323846264338327950288419716939937510582097494459230;
// priority_queue<t>
ll max(ll a , ll b){ if(a>b)return a; return b;}
ll min(ll a , ll b){ if(a<b)return a; return b;}
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
ll pct(ll x) { return __builtin_popcount(x); } // # of bits set
ll poww(ll a, ll b) { ll res=1; while(b) { if(b&1)	res=(res*a); a=(a*a); b>>=1; } return res; }
ll modI(ll a, ll m=mod) { ll m0=m,y=0,x=1;  if(m==1) return 0;  while(a>1)  { ll q=a/m; ll t=m;  m=a%m;  a=t; t=y; y=x-q*y;  x=t; } if(x<0) x+=m0; return x;}
ll powm(ll a, ll b,ll m=mod) {ll res=1;	while(b) {	if(b&1)	res=(res*a)%m;	a=(a*a)%m; b>>=1;	}	return res;}
//*******************************************************************************************************************************************//
vector<pair<ll,pll>>v[100001];
bool vis[100001]={0};
ll dp[100001];
ll n;
ll calc(ll st, ll c, ll d)
{
   
    return max(st,sqrt(d));
}
void bfs(ll s)
{
    ll i,j,d,x,y;
    for(i=1;i<=n;i++)dp[i]=lmax;
    priority_queue<pll>q;
    q.push({0,1});
    dp[1]=0;
    while(q.size())
    {
        x=q.top().s;
        q.pop();
        if(vis[x])
            continue;
        vis[x]=1;
        for(auto u:v[x])
            if(u.f!=x)
        {
            d=calc(dp[x],u.s.f,u.s.s);
            d=u.s.f+fdiv(u.s.s,d+1)+d;
            
            
            if(d<dp[u.f])
            {//c2(u.f,d);
                dp[u.f]=d;
             q.push({-1*dp[u.f],u.f});
            }
        }
    }
    
}
void iamzeus()
{ ll i,j,x=0,y,ans=0,m,d,cnt=0,z,c=2,k;
  
 cin>>n>>m;
 for(i=0;i<m;i++)
 {
     cin>>x>>y>>z>>d;
     v[x].pb({y,{z,d}}),v[y].pb({x,{z,d}});
 }
 bfs(1);
 if(dp[n]==lmax)
     iota;
 else
 c1(dp[n]);
 
};
int main()
{fast;
    int t;
 t=1;
//cin >>t;
 while(t--)
     iamzeus();
}

#include<bits/stdc++.h>

#define int long long
using namespace std;
#define rep(i, n) for(int i=0;i<(n);++i)
typedef pair<int, int> pii;
const int INF = 1l << 60;

int N, M;
vector<pair<int, pii>> G[100010];
int dist[100010];

//時刻tかそれ以降にCi=c,Di=dの道の通行を始めるとき、最短で到着する時刻
int earliest(int c, int d, int t) {
    int T = sqrt(d) - 1;
    int T2 = sqrt(d);
    if (T < t)T = t;
    if (T2 < t)T2 = t;
    return min({t + c + d / (t + 1), T + c + d / (T + 1), T2 + c + d / (T2 + 1)});
}

void dijkstra() {
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    dist[0] = 0;
    for (int i = 1; i < N; ++i)dist[i] = INF;
    pq.emplace(dist[0], 0);
    while (!pq.empty()) {
        pii p = pq.top();
        pq.pop();
        int v = p.second;
        if (dist[v] < p.first)continue;
        for (auto e:G[v]) {
            int to = e.first;
            int c = e.second.first;
            int d = e.second.second;
            int time = earliest(c, d, dist[v]);
            if (dist[to] > time) {
                dist[to] = time;
                pq.emplace(dist[to], to);
            }
        }
    }
}

signed main() {
    cin >> N >> M;
    rep(i, M) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        --a, --b;
        G[a].emplace_back(b, pii(c, d));
        G[b].emplace_back(a, pii(c, d));
    }
    dijkstra();
    if (dist[N - 1] == INF)cout << -1 << endl;
    else cout << dist[N - 1] << endl;
    return 0;
}
