#include<bits/stdc++.h>
using namespace std;
template <class T> ostream &operator << (ostream &os, const vector<T> &p) { os << "["; for (auto&it : p) os << it << " "; return os << "]";}
template <class S, class T> ostream &operator << (ostream &os, const pair<S, T> &p) { return os << "(" << p.first << "," << p.second << ")";}
#ifndef ONLINE_JUDGE
#define deb(...) dbs(#__VA_ARGS__,__VA_ARGS__)
template <class T> void dbs(string str, T t) { cerr << str << ":" << t << "\n";}
template<class T, class...S> void dbs(string str, T t, S... s) { int idx = str.find(','); cerr << str.substr(0, idx) << ":" << t << ","; dbs(str.substr(idx + 1), s...);}
#else
#define deb(...){}
#endif
#define int long long
#define ld long double
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ini(x, y) memset(x, y, sizeof(x))
#define pr(x) {cout << x << '\n'; return;}
#define nl cout<< '\n'
#define rep(i,n) for(int i = 0; i < n; i++)
#define re(i,n) for(int i = 1; i <= n; i++)
#define vi vector<int>
#define pii pair<int, int>
#define vii vector<pii>
template<class T> inline T Bit(T x, int i) { return (x >> i) & 1;}
template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }
const int N = 1e5 + 3; // check the limits

void solve() {
	int n, m; cin >> n >> m;
	vector<pair<int, pii>> g[n + 1];
	rep(i, m) {
		int x, y, c, d;
		cin >> x >> y >> c >> d;
		g[x].pb({y, {c, d}});
		g[y].pb({x, {c, d}});
	}
	set<pii> s;
	s.insert({0, 1});
	vi dis(n + 1, 1e18);
	dis[1] = 0;
	while (sz(s)) {
		pii p = *s.begin();
		s.erase(s.begin());
		int v = p.se, w = p.fi;
		for (auto u : g[v]) {
			int x = u.fi, c = u.se.fi, d = u.se.se;
			vi cur{w};
			for (int i = sqrt(d) - 1; i <= sqrt(d + 1); i++) {
				if (w >= i) continue;
				cur.pb(i);
			}
			if (d >= w) cur.pb(d);
			if (d - 1 >= w) cur.pb(d - 1);
			for (auto i : cur) {
				int time = i + (d / (i + 1)) + c;
				if (dis[x] > time) {
					s.erase({dis[x], x});
					dis[x] = time;
					s.insert({dis[x], x});
				}
			}
		}
	}
	int ans = dis[n];
	if (ans >= 1e14) ans = -1;
	cout << ans << '\n';
}

signed main() {
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	//int t; cin >> t;
	//while (t--)
	solve();
}
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr long long MOD = 1000000007;
constexpr long long MOD2 = 998244353;
constexpr long long INF = 1LL << 60;
const long double PI = acosl(-1.0);
constexpr long double EPS = 1e-11;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
ll c[100000 + 2], d[100000 + 2];
struct edge {
    long long to, cost, strict;
};
struct graph{
    long long v;
    vector<vector<edge>> adj;
    vector<long long> dist, used;

    graph(long long n) {
        init(n);
    }
    void init(long long n){
        v = n;
        adj.resize(v);
        dist.assign(v, INF);
        used.assign(v, 0LL);
    }
    void add_edge(long long stt,long long gol,long long cst,long long ks){
        edge e;
        e.to = gol;
        e.cost = cst;
        e.strict = ks;
        adj[stt].emplace_back(e);
    }
	void dijkstra(long long stt){
        for (long long i = 0; i < v;i++){
            dist[i] = INF;
        }
        dist[stt] = 0;
		//cost,to
        priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> pq;
        pq.push({0LL, stt});
		while(!pq.empty()){
            auto p = pq.top();
            pq.pop();
            long long vertex = p.second;
            if (dist[vertex] < p.first) continue;
            for (auto e : adj[vertex]) {
                ll time = dist[vertex];
                if (time < sqrtl(e.strict) - 1) time = sqrtl(e.strict);
                time += e.strict / (time + 1);
                if (chmin(dist[e.to], time + e.cost)) pq.push({dist[e.to], e.to});
            }
        }
    }
    long long prim(){
        priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> pq;
        long long res = 0;
        pq.push({0LL, 0LL});
        while(!pq.empty()){
            long long cst = pq.top().first, vertex = pq.top().second;
            pq.pop();
            if (used[vertex]) continue;
            used[vertex] = 1;
            res += cst;
            for(auto e:adj[vertex]){
                if (!used[e.to]) pq.push({e.cost, e.to});
            }
        }
        return res;
    }
};
int main(){
    ll n, m;
    cin >> n >> m;
    graph g(n);
    for (ll i = 0; i < m; i++) {
        ll a,b;
        cin >> a >> b >> c[i] >> d[i];
        a--;
        b--;
        g.add_edge(a, b, c[i], d[i]);
        g.add_edge(b, a, c[i], d[i]);
    }
    g.dijkstra(0);
    if(g.dist[n-1]==INF){
        cout << "-1" << endl;
    }
    else
        cout << g.dist[n - 1] << endl;
}