// E - Rush Hour 2
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define vec vector
using vl = vec<ll>;
#define rep(i,e) for(int i=0;i<(e);++i)
using PR = pair<ll,int>;

// 本問用に修正
// dijkstra O(|E|log|V|)
int V;
vec<tuple<int,int,int,int>> E;
vec<vec<int>> G;
ll INF = 1e18;

ll cost(ll c, ll d, ll t){
	ll ok = t, ng = d+1;
	while(ng - ok > 1){
		ll m = (ok+ ng) / 2;
		(m*(m+1) < d? ok:ng) = m;
	}
	return ok + c + d / (ok+1);
}

vl dijkstra(int s){
	vl dist(V, INF);
	dist[s] = 0;
	priority_queue<PR, vec<PR>, greater<PR>> pq;
	pq.push({0, s});
	while(pq.size()){
		auto[t, v] = pq.top(); pq.pop();
		if(dist[v] < t) continue;
		for(int&i:G[v]){
			auto&[a, b, c, d] = E[i];
			int u = a; // b->a
			if(u == v) u = b; // a->b
			ll nt = cost(c, d, dist[v]);
			if(dist[u] <= nt) continue;
			dist[u] = nt;
			pq.push({nt, u});
		}
	}
	return dist;
}

int main(){
	int m; cin>>V>>m;
	G.resize(V);
	rep(i, m){
		int a, b, c, d; cin>>a>>b>>c>>d; --a, --b;
		E.emplace_back(a, b, c, d);
		G[a].push_back(i), G[b].push_back(i);
	}
	ll ans = dijkstra(0)[V-1];
	if(ans == INF) ans = -1;
	cout<< ans <<endl;
}

#include<bits/stdc++.h>
#define int long long
#define nb 200010
using namespace std;

bool vis[nb];
int n, m, cnt, head[nb], dis[nb];
struct edge{int to, next, c, d;}e[nb];

void add_edge(int u, int v, int c, int d){
	e[++cnt].to = v;
	e[cnt].c = c;
	e[cnt].d = d;
	e[cnt].next = head[u];
	head[u] = cnt;
}

struct node{
	int id, d;
	bool operator < (const node &tmp) const{
		return tmp.d < d;
	}
};

priority_queue<node> q;

void dijkstra(){
	memset(dis, 0x3f, sizeof(dis));
	dis[1] = 0;
	q.push((node){1, 0});
	while(!q.empty()){
		node tmp = q.top();
		q.pop();
		int u = tmp.id;
		if(vis[u]) continue;
		vis[u] = 1;
		for(int i = head[u]; i; i = e[i].next){
			int c = e[i].c, d = e[i].d, v = e[i].to, s = sqrt(d), t;
			if(dis[u] < s) t = s + d / (s + 1) + c;
			else t = dis[u] + d / (dis[u] + 1) + c;
			if(dis[v] > t){
				dis[v] =  t;
				if(!vis[v]){
					q.push((node){v, dis[v]});
				}
			}
		}
	}
}

signed main(){
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int u, v, c, d;
		cin >> u >> v >> c >> d;
		add_edge(u, v, c, d);
		add_edge(v, u, c, d);
	}
	dijkstra();
	cout << (dis[n] > 1e16 ? -1 : dis[n]);
	return 0;
}