#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<ll, int>;
using T = tuple<int,int,int>;
int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<T>> g(n);
    rep(i, m)
    {
        ll a, b,c,d;
        cin >> a >> b >> c >> d;
        --a, --b;
        g[a].emplace_back(b, c, d);
        g[b].emplace_back(a, c, d);

    }

    const ll INF = 1e18;
    vector<ll> d(n, INF);
    priority_queue<P, vector<P>, greater<P>> pq;
    pq.emplace(0, 0);
    d[0] = 0;

    while (!pq.empty())
    {
        ll c = pq.top().first;
        int s = pq.top().second;
        pq.pop();
        if (d[s] < c) continue;
        for (const auto& gi: g[s])
        {
            int e, ci, di;
            tie(e, ci, di) = gi;
            int t = round(sqrt(di));
            ll next = d[s] + ci + di / max((ll)t, d[s] + 1) + max(0LL, t - 1 - d[s]);
            if (d[e] <= next) continue;
            d[e] = next;
            pq.emplace(d[e], e);
        }
    }
    ll ans = d[n - 1];

    if (ans == INF) cout << -1 << endl;
    else cout << ans << endl;
    
    return 0;
}

// #pragma GCC target ("avx,avx2")
// #include <bits/extc++.h>
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

#define f first
#define s second

using namespace std;
// using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
// typedef tree<int, null_type, less<int>, 
// rb_tree_tag, tree_order_statistics_node_update> oset;
//========================================================
const int N = 1e5+5, K = 19, M = 5e4+5, mod = 1e9+7, len = 30, inf = 0x3f3f3f3f;
int n, m;
ll dist[N];

vector<pair<int, pair<ll, ll>>> adj[N];

void dijkstra(int src)
{
	priority_queue<pair<ll, int>> q;

	fill(dist, dist+n, 1e18);

	q.push({0, src});
	dist[src] = 0;

	while(!q.empty())
	{
		auto t = q.top();
		q.pop();

		int u = t.s;
		if(dist[u] != -t.f)
			continue;
		if(u == n-1)
			break;
		for(auto e : adj[u])
		{
			ll v = e.f, c = e.s.f, d = e.s.s;
			auto dis = [&](ll T)
			{
				ll res = c + ll(d / (T + 1)) + T;
				return res;
			};

			ll s = 1ll * sqrt(d) - 1;
			s = max(s, 0LL);
			if(dist[u] > s)
				s = dist[u];
			ll D = min(dis(s), dis(s+1));
			// assert(D > 0);
			if(dist[v] > D)
				dist[v] = D, q.push({-D, v});
		}
	}
	if(dist[n-1] == 1e18)
		dist[n-1] = -1;
}

void run_case()
{
	scanf("%d %d", &n, &m);
	for(int i=0, u, v, c, d; i<m; i++)
	{
		scanf("%d %d %d %d", &u, &v, &c, &d);
		adj[u-1].push_back({v-1, {c, d}});
		adj[v-1].push_back({u-1, {c, d}});
	}

	dijkstra(0);
	printf("%lld\n", dist[n-1]);
}

int main()
{
    // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // freopen("input.txt", "rt", stdin);
    // freopen("output.txt", "wt", stdout);
    int t;
    t = 1;
    // cin >> t;
    while(t--)
        run_case();
}
