#include <bits/stdc++.h>
using namespace std;
#define intt long long int
#define F first 
#define S second
#define pb push_back
const int N=1e5+5;
vector<pair<int,pair<int,int>>> adj[N];
intt vis[N],tim[N];
int n,m;
const intt INF=1e15;

intt calc(intt c,intt d,intt t)
{
  //  cout<<c<<" "<<d<<" "<<t<<endl;
    intt ret=t+c+d/(t+1);
    intt rt=sqrt(d);
    if(t>rt){  return ret;}

    t=rt;
    ret=min(ret,t+c+d/(t+1));    
    t--;
    if(t>=0) ret=min(ret,t+c+d/(t+1));
   // cout<<"dd   "<<ret<<endl;
    return ret;
}

void dijkstra(int s)
{
    set<pair<intt,intt>> sett; // time, city index
    sett.insert({0,s});
    for(int i=1;i<=n;i++) 
    {
        tim[i]=INF;
    }
    tim[1]=0;

    while(!sett.empty())
    {
        pair<intt,intt> aa=*sett.begin(); 
        sett.erase(sett.begin());
        if(tim[aa.S]<aa.F)
        { continue;}

        //assert(tim[aa.S]==aa.F);

        int pp=aa.S,tt=aa.F;
        for(auto ss:adj[pp])
        {   
            int ind=ss.F;
            int cc=ss.S.F,dd=ss.S.S;

            intt time_=calc(cc,dd,tim[pp]);
            //cout<<time_<<endl;
            if(time_<tim[ind])
            {
                tim[ind]=time_;
                
                sett.insert({time_,ind});
            }
        }


        
    }
}
int main()
{
   cin>>n>>m;

   for(int i=0;i<m;i++)
   {
       int a,b,c,d;cin>>a>>b>>c>>d;
       if(a==b) continue; 
       adj[a].pb({b,{c,d}});
       adj[b].pb({a,{c,d}});
   } 
   dijkstra(1);

   // for(int i=1;i<=n;i++) cout<<tim[i]<<endl;

    if(tim[n]==INF)cout<<-1<<endl;
    else
   cout<<tim[n]<<endl;
    return 0;
}

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define double long double
#define rbtree __gnu_pbds::tree<int,__gnu_pbds::null_type,less<int>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>
#define int ll
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);
#define pb push_back
#define ALL(X) X.begin(),X.end()
#define F(i,n)  FF(i,0,n)
#define F1(i,n)  FF(i,1,n+1)
#define FF(i,n,m) for(int i=(int)n;i<(int)m;++i)
#ifndef LOCAL
//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#else
#endif // LOCOL
//#define mp make_pair
using namespace std;
//using namespace __gnu_pbds;
template<typename T> bool remax(T& a, const T& b) {return b>a?a=b,1:0;}
template<typename T> bool remin(T& a, const T& b) {return b<a?a=b,1:0;}
inline ostream& operator << (ostream& os,__int128_t a){if(a==0) {return (os<<'0');}bool flag=0;if(a<0) {a=-a,flag=1;}string s;while(a){s+=a%10+'0';a/=10;}s+=flag?"-":"";reverse(ALL(s));return os<<s;}
inline istream& operator >>(istream& is,__int128_t& a){string s;cin>>s;a=0;for(auto c:s) a=a*__int128_t(10)+__int128_t(c-'0');return is;}
template<typename T,typename P> inline ostream& operator << (ostream& os,pair<T,P> a){os<<a.first<<" "<<a.second; return os;}
template<typename T,typename P> inline istream& operator >> (istream& is,pair<T,P> &a){is>>a.first>>a.second; return is;}
using ll=long long;
using ull=unsigned long long;
using int128= __int128_t;
using uint128= __uint128_t;
using pii =pair<int,int>;
const double pi=acos(-1);
const int N=1E5+5;
const ll M=1000000000;
const ll INF_64=0x3f3f3f3f3f3f3f3f;
const int INF_32=0x3f3f3f3f;
const int16_t INF_16=0x3f3f;
const int klog=20;
const int mod=998244353;//1E9+7
const double eps=1E-8;
void gen(){
}

int d[N]{};
vector<pair<int,pii>> g[N];
int dis(int c,int d,int t){
    double l=0,r=1E14;
    F(_,100){
        double m1=l+(r-l)/3.0,m2=r-(r-l)/3.0;
        double mv1=t+m1+c+(d/(t+m1+1.0));
        double mv2=t+m2+c+(d/(t+m2+1.0));
        if(mv1==mv2) l=m1,r=m2;
        else if(mv1>mv2) l=m1;
        else r=m2;
    }
    int re=INF_64;
    int L=l,R=r;
    FF(j,L-3,R+3)
        if(j>=0)remin(re,t+j+c+(d/(t+j+1)));
    return re;
}
void sol(){
    int n,m;cin>>n>>m;
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    memset(d,0x3f,sizeof(d));
    d[0]=0;pq.push({0,0});
    F(i,m){
        int a,b,C,D;cin>>a>>b>>C>>D;
        a--,b--;
        g[a].pb({b,{C,D}});
        g[b].pb({a,{C,D}});
    }
    while(pq.size()){
        auto [val,a]=pq.top();pq.pop();
        if(val!=d[a]) continue;
        for(auto &[b,tt]:g[a]){
            if(remin(d[b],dis(tt.first,tt.second,d[a])))
                pq.push({d[b],b});
        }
        assert(d[a]==val);
    }
    //F(i,n) cout<<d[i]<<" ";
    //cout<<"\n";
    assert(d[n-1]>=0);
    cout<<(d[n-1]>=INF_64?-1:d[n-1])<<"\n";
}
int32_t main(){
    #ifdef LOCAL
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    #endif // LOCAL
    IOS;
    int t=1;
    gen();
    //cin>>t;
    FF(i,1,t+1){
        //cout<<"Case #"<<i<<": ";
        sol();
    }
}
