#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iostream>
#include <sstream>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <vector>

using namespace std;

typedef long double LD;
typedef pair<int64_t, int64_t> II;
typedef pair<int64_t, II> III;

static const int64_t INF = 1LL << 60;


struct Dijkstra {
	vector<vector<II>> edges;
	vector<int64_t> c;
	vector<int64_t> d;

	Dijkstra(int64_t size) : edges(size) { }

	void add_edges(std::vector<int64_t>& A, std::vector<int64_t>& B) {
		for (int i = 0; i < A.size(); ++i) {
			add_edge(A[i], B[i], i);
		}
	}

	void add_edge(int64_t a, int64_t b, int64_t c = 1) {
		edges[a].push_back({ b, c });
		edges[b].push_back({ a, c });
	}

	vector<int64_t> get_min_costs(int64_t start) {
		vector<int64_t> min_costs(edges.size(), 1LL << 60);
		priority_queue<pair<int64_t, int64_t>, vector<pair<int64_t, int64_t>>, greater<>> q;
		min_costs[start] = 0;
		q.emplace(make_pair(0, start));
		while (!q.empty()) {
			pair<int64_t, int64_t> top = q.top();
			q.pop();
			int64_t cost = top.first, node = top.second;
			if (cost > min_costs[node]) continue;
			for (auto kv : edges[top.second]) {
				int64_t next_node = kv.first, i = kv.second;
				int64_t cc = c[i], dd = d[i];
				int64_t next_cost = top.first + cc + dd / (cost + 1);

				int64_t t = cost;
				int64_t sq = sqrt(dd);
				t = max(t, sq);

				auto calc = [&](int64_t t) {
					return cc + dd / (t + 1) + t;
				};

				int64_t left = t, right = t + 1e9;
				for (int tt = 0; tt < 100; ++tt) {
					int64_t p = calc((left * 2 + right) / 3);
					int64_t q = calc((left + right * 2) / 3);

					if (calc((left * 2 + right) / 3) <= calc((left + right * 2) / 3)) {
						right = (left + right * 2) / 3;
					} else {
						left = (left * 2 + right) / 3;
					}
				}
				for (int64_t tt = 0; tt < 6; ++tt) {
					next_cost = min(next_cost, calc(left + tt));
				}

				if (next_cost < min_costs[next_node]) {
					min_costs[next_node] = next_cost;
					q.emplace(make_pair(next_cost, next_node));
				}
			}
		}
		return min_costs;
	}
};

int64_t solve(int64_t N, int64_t M, std::vector<int64_t> A, std::vector<int64_t> B, std::vector<int64_t> C, std::vector<int64_t> D) {
	Dijkstra d(N);
	d.c = C;
	d.d = D;
	d.add_edges(A, B);
	vector <int64_t> costs = d.get_min_costs(0);
	int64_t ans = costs[N - 1];
	return ans < (1LL << 60) ? ans : -1;
}

int main() {
#if DEBUG || _DEBUG
	freopen("in.txt", "r", stdin);
	//	freopen("in_1.txt", "r", stdin);
#endif
	int64_t N, M;
	std::cin >> N >> M;
	std::vector<int64_t> A(M), B(M), C(M), D(M);
	for (int i = 0; i < M; i++) {
		std::cin >> A[i] >> B[i] >> C[i] >> D[i];
		--A[i], --B[i];
	}
	cout << solve(N, M, std::move(A), std::move(B), std::move(C), std::move(D)) << endl;
	return 0;
}

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

//wierd debugging stuff
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << "\n" ; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
//end of weird debugging stuff

using ll = long long;
using ld = long double;
using vi = vector<int>;
using ii = pair<int,int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;

 
#define F_OR(i, a, b, s) for (int i = (a); ((s) > 0 ? i < (b) : i > (b)); i += (s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define rep(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define each(x) for(auto& a: x)
#define ar array
#define pb push_back
#define vt vector

template<class T> bool umin(T& a,const T& b){return b<a?a=b,1:0;}
template<class T> bool umax(T& a,const T& b){return b>a?a=b,1:0;}

template<class A> void read(vt<A>& v);
template<class A, size_t S> void read(ar<A, S>& a);
template<class T> void read(T& x) {cin>>x;}
void read(double& d) {string t;read(t);	d=stod(t);}
void read(long double& d) {	string t;read(t);d=stold(t);}
template<class H, class... T> void read(H& h, T&... t) {read(h);read(t...);}
template<class A> void read(vt<A>& x) {	each(x)read(a);}

// no change 
const ll MOD = 1e9+7;  
/*
 p = each(x);
 */

void Solve(){
	int n,m;
	cin >> n >> m;
	vector<tuple<ll,ll,ll>> adj[n+1];
	for(int i = 0;i<m;i++){
		ll a,b,c,d;
		read(a,b,c,d);
		adj[a].push_back(make_tuple(b,c,d));
		adj[b].push_back(make_tuple(a,c,d));
	}
	priority_queue<ii,vt<ii>,greater<ii>> q;
	q.push(make_pair(0,1));
	ll inf = 2e18;
	ll x,y,t;
	vl dist(n+1,inf);
	dist[1] = 0;

	while(!q.empty()){
		auto p = q.top();q.pop();
		x = p.first ,y = p.second;
		if(x > dist[y])continue;
		for(auto [b,c,d] : adj[y]){
			ll t = dist[y];
			ll k = sqrt((double)d);
			ll x = inf;
			rep(3){
				ll s = k -2 +i;
				if(s<0 || s < t)continue;
				x = min(x,c+(s-t)+ d/(s+1));
			}
			x = min(x,c+d/(t+1));
			if(x+t < dist[b]){
				dist[b] = x+t;
				q.push(make_pair(x+t,b));
			}
		}
	}

	if(dist[n] == inf ){
		cout << -1 << "\n";
		return;
	}
	cout << dist[n] << "\n";
	






}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T = 1;
	// cin >> T;		//cmt if one test case
    rep(T)Solve();
}
