#include "bits/stdc++.h"
using namespace std;

// 定義
typedef long long         ll;
typedef pair<ll, ll>      P;
#define ALL(x)            (x).begin(),(x).end()
#define REP(i, n)         for(ll i = 0 ; i < (ll)n ; ++i)
#define REPN(i, m, n)     for(ll i = m ; i < (ll)n ; ++i)
#define VL                vector<ll>
#define VVL               vector<vector<ll>>
#define VVVL              vector<vector<vector<ll>>>
#define INF               (ll)2e9
#define INF_LL            1LL<<60
//#define MOD             998244353
#define MOD               1000000007

ll Ceil(ll val, ll div)   { return (val + div - 1) / div; }
ll CeilN(ll val, ll div)  { return Ceil(val, div) * div; }
ll FloorN(ll x, ll n)     { return (x - x % n); }
bool IsOdd(ll x)          { return ((x & 1) == 1); }
bool IsEven(ll x)         { return ((x & 1) == 0); }

// 枝定義
struct Edge
{
	ll	to;
	ll	dist;
	ll	rash;
	Edge(){}
	Edge(int to, ll dist, ll rash) : to(to), dist(dist), rash(rash){}
};

// グラフ定義(二次元配列)
template <class E>
using Graph = vector<vector<E>>;

// ダイクストラ
class Dijkstra
{
public:
	// res[i] = sからiまでの最短距離
	vector<ll> res;

	// 復元パス
	//	vector<int> pathList;

	vector<ll> pathRev;
	const ll inf = 1e15;

	ll getVal(ll stTime, ll D) {

		ll low = floor((sqrt(D)) - 1) - 2;
		low = max(low, stTime);
		
		ll ans = inf;
		REPN(t, low, low + 10) {
			ll rashTime = t + D / (t + 1);
			ans = min(ans, rashTime);
		}
		return ans;
	}

public:
	template<class E>
	Dijkstra(const Graph<E> &G, int startFrom)
	{
		int V = (int)G.size();
		res = vector<ll>(V, inf);
		pathRev.resize(V, -1);

		using P = pair<ll, int>;
		priority_queue<P, vector<P>, greater<P>> que;
		que.push(P(0, startFrom));
		res[startFrom] = 0;

		while (!que.empty()) {
			P p = que.top(); que.pop();
			int egdeFrom = p.second;

			// 違う最短距離がキューにあるのでスキップ
			if (res[egdeFrom] < p.first) {
				continue;
			}

			// 最短距離を更新
			for (const E &edge : G[egdeFrom]) {
				ll rashCost = getVal(p.first, edge.rash);
				ll nextDist = edge.dist + rashCost;
				if (nextDist < res[edge.to]) {
					res[edge.to] = nextDist;
					pathRev[edge.to] = egdeFrom;
					que.push(P(nextDist, edge.to));
				}
			}
		}
	}

	// 経路を取得する
	vector<ll> getPath(ll dstPos)
	{
		vector<ll> pathList;

		while (dstPos != -1) {
			pathList.push_back(dstPos);
			dstPos = pathRev[dstPos];
		}
		reverse(pathList.begin(), pathList.end());
		return pathList;
	}
};

// 処理
void Solve()
{
	int N, M;
	cin >> N >> M;
	Graph<Edge>	G(N);
	REP(i, M) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		a--, b--;
		G[a].emplace_back(Edge(b, c, d));
		G[b].emplace_back(Edge(a, c, d));
	}

	Dijkstra dijk(G, 0);
	ll ans = dijk.res[N - 1];
	if (ans == 1e15) {
		cout << -1 << endl;
	} else {
		cout << ans << endl;
	}
}

// メイン
int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Solve();
	return 0;
}

#include<bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define MP make_pair
#define PB emplace_back
using namespace std;
const int MAX_N = 100001;
int C[MAX_N], D[MAX_N];
vector<pair<int, int>> e[MAX_N];
long long dis[MAX_N];
long long f(long long v, int eid) {
    int sq = sqrt(D[eid]+(long double)0.1);
    while(sq * sq < D[eid]) { sq++; }
    if((v + 1) <= sq) {
        return sq - 1 + C[eid] + D[eid] / sq;
    } else {
        return v + C[eid] + D[eid] /  (v + 1);
    }
}
void solve() {
    int N, M;
    scanf("%d%d", &N, &M);
    for(int i = 0; i < M; i++) {
        int A, B;
        scanf("%d%d%d%d", &A, &B, &C[i], &D[i]);
        e[A].PB(MP(B,i));
        e[B].PB(MP(A,i));
    }
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>>pq;
    pq.push(MP(0, 1));
    for(int i = 2; i <= N; i++) {
        dis[i] = 1e18;
    }
    while(!pq.empty()) {
        auto x = pq.top();
        pq.pop();
        if(x.second == N) {
            printf("%lld\n", x.first);
            return;
        }
        if(dis[x.second] < x.first) {
            continue;
        }
        for(auto ee: e[x.second]) {
            int y, eid;
            tie(y, eid) = ee;
            long long nxt_v = f(x.first, eid);
            if(dis[y] > nxt_v) {
                dis[y] = nxt_v;
                pq.push(MP(nxt_v, y));
            }
        }
    }
    puts("-1");
}
int main() {
    solve();
    return 0;
}
