#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,m; cin >> n >> m;
    vector<vector<pair<int,int>>> g(n);
    vector<int> c(m),d(m);
    for(int i=0;i<m;i++){
        int x,y; cin >> x >> y;
        x--,y--;
        g[x].push_back({y,i});
        g[y].push_back({x,i});
        cin >> c[i] >> d[i];
    }
    vector<ll> dp(n,1e18);
    dp[0]=0;
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
    pq.push({0,0});
    auto cost=[&](int j,ll ti)->ll{
        ll res=d[j]/(ti+1);
        ll p=sqrt(d[j]);
        for(ll T=max(ti,p-15);T<=p+15;T++){
            res=min(res,T-ti+d[j]/(T+1));
        }
        return res+c[j];
    };
    while(pq.size()){
        auto p=pq.top(); pq.pop();
        if(dp[p.second]!=p.first)continue;
        int s=p.second;
        for(auto to:g[s]){
            ll c=cost(to.second,p.first);
            int t=to.first;
            if(dp[t]>c+p.first){
                dp[t]=c+p.first;
                pq.push({dp[t],t});
            }
        }
    }
    if(dp[n-1]==1e18)dp[n-1]=-1;
    cout << dp.back() << endl;
}
#include <bits/stdc++.h>
#define REP(i, nn ) for(int i = 0 ; i < (int) nn; i++)
#define REPS(i, ss, nn ) for(int i = ss ; i < (int) nn; i++)
#define REV(i, ss, nn ) for(int i = ss ; i >= nn; i--)
#define deb(x) std::cout << #x << " " << x << endl;
#define debl(x) std::cout << #x << " " << x << " ";
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
namespace std{
    template<class Fun>
    class y_combinator_result{
        Fun fun_;
        public:
            template<class T>
            explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)){}
            template<class ...Args>
            decltype(auto) operator()(Args&&...args){
                return fun_(std::ref(*this), std::forward<Args>(args)...);
            }
    };
    template<class Fun>
    decltype(auto) y_combinator(Fun && fun){
        return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
    }
};
template<typename T>
bool umax(T& a, T b){
    bool ret = a < b;
    if(ret) a = b;
    return ret;
}
template<typename T>
bool umin(T& a, T b){
    bool ret = a > b;
    if(ret) a = b;
    return ret;
}
struct edge{
    int to; ll cost;
    int from;
    edge(){ edge(0,0);}
    edge(int to_, ll cost_) : to(to_), cost(cost_){}
    edge(int to_, int from_, ll cost_) : to(to_), cost(cost_), from(from_){}
};

template<typename... T>
void read(T& ... a){
    ((cin >> a),...);
}

template<typename... T>
void write(T... a){
    ((cout << a),...);
}


template<typename T>
vector<T> read_array(int sz){
    vector<T> ret(sz);
    for(auto & x : ret) cin >> x;
    return ret;
}

int m, n;
constexpr int mxN = 1e5;
vector<array<ll,3>> adj[mxN];
ll dist[mxN];

ll f(ll d, ll t0, ll x){
    return t0 + x + d / (t0 + 1 + x);
}


ll best_time(ll d, ll t0){
    ll left = ceil(sqrtl(d));
    ll ans =  f(d, t0, 0);

    for(ll x = max(0ll, left - 10) ; x <= left + 10; x++){
        umin(ans, f(d, t0, x));
    }
    return ans;
}

void solve(){
    read(n, m);
    REP(i, m){
        ll a, b, c, d;
        read(a, b, c, d);
        a--; b--;
        // if(a == b) continue;
        adj[a].push_back({b, c, d});
        adj[b].push_back({a, c, d});
    }
    ll INF = 3e14;
    REP(i, n) dist[i] = INF;
    dist[0] = 0;
    set<pair<ll,ll>> st;
    st.insert({dist[0], 0});
    while(st.size()){
        auto [t, idx] = *st.begin();
        st.erase(st.begin());
        if(dist[idx] < t) continue;
        // debl(idx) deb(t)
        for(auto edge : adj[idx]){
            auto [nxt, c, d] = edge;
            ll best = best_time(d, t);
            best += c; 
            if(best < dist[nxt]){
                dist[nxt] = best;
                st.insert({dist[nxt], nxt});
            }
        }
    }
    if(dist[n-1] >= INF){
        write(-1);
        return;
    }
    write(dist[n-1]);
}
int main()
{
    //making data IO Fast
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    /****************************/
    int T = 1;
    // cin >> T;
    while(T--)
        solve();
    return 0;
}

