#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxN = 1e5 + 5;
vector <tuple<int, int, int>> adj[maxN];

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	int n, m;
	cin >> n >> m;

	for(int i = 0; i < m; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;

		adj[a].emplace_back(b, c, d);
		adj[b].emplace_back(a, c, d);
	}

	priority_queue <pair<ll, int>, vector <pair<ll, int>>, greater<pair<ll, int>>> pq;
	vector <ll> dist(n + 1, 1e18);

	pq.emplace(0, 1);
	dist[1] = 0;

	while(!pq.empty()) {
		auto [val, x] = pq.top();
		pq.pop();

		if(dist[x] < val) continue;

		for(auto &[v, c, d] : adj[x]) {
			ll new_dist = 0;
			ll sq = sqrt(d);

			if(sq * sq != d) sq++;
			sq--;

			if(val < sq) {
				new_dist = sq - val + c + d / (sq + 1);
			}
			else {
				new_dist = c + d / (val + 1);
			}

			if(dist[v] > val + new_dist) {
				dist[v] = val + new_dist;
				pq.emplace(dist[v], v);
			}
		}
	}
	cout << (dist[n] == 1e18 ? -1 : dist[n]);
}
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <functional>

// AtCoder
// #include <atcoder/all>
// using namespace atcoder;

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...)
#endif

#define rep_(i, a_, b_, a, b, ...) for (int i = (a), i##_len = (b); i < i##_len; ++i)
#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define reprev_(i, a_, b_, a, b, ...) for (int i = (b)-1, i##_min = (a); i >= i##_min; --i)
#define reprev(i, ...) reprev_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define all(x) (x).begin(), (x).end()
template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
#define fls(x) (64 - __builtin_clzll(x))
#define pcnt(x) __builtin_popcountll(x)
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <ll,int> P;
typedef long double ld;

ll find_bottom (ll d) {
    if (d <= 1) return 0;
    if (d == 2) return 1;
    ll l = 0, r = d + 1;
    while (r - l > 1) {
        ll m = (r + l) >> 1;
        (m * (m + 1) <= d ? l : r) = m;
    }
    --l;
    if (l + d / (l + 1) >= l + 1 + d / (l + 2)) ++l;
    if (l + d / (l + 1) >= l + 1 + d / (l + 2)) ++l;
    return l;
}

struct edge {
    ll to, c, d, bottom;
    edge (ll to, ll c, ll d) : to(to), c(c), d(d), bottom(find_bottom(d)) {};
};

constexpr ll INF = 1e18;
int main (void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m; cin >> n >> m;
    vector<vector<edge>> g(n);
    rep (_, m) {
        int 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);
    }
    rep (i, 21) eprintf("%lld ", find_bottom(i));

    vector<ll> d(n, INF); d[0] = 0;
    priority_queue<P, vector<P>, greater<P>> pq; pq.emplace(0, 0);
    while (!pq.empty()) {
        auto [dist, u] = pq.top(); pq.pop();
        if (dist > d[u]) continue;
        for (auto &e : g[u]) {
            ll t = max((ll)e.bottom, d[u]);
            if (chmin(d[e.to], e.c + t + e.d / (t + 1))) {
                pq.emplace(d[e.to], e.to);
            }
        }
    }
    cout << (d.back() >= INF ? -1 : d.back()) << '\n';
    return 0;
}