#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
struct edge{ll b,c,d;};
int n;
vector<edge>graph[100005];
vector<int>g[100005];
bool v[100005];
void dfs(int cur){
	v[cur] = 1;
	for(int nxt:g[cur]){
		if(!v[nxt]) dfs(nxt);
	}
}
ll ternary(ll t,ll d){
	ll h = sqrt(d);
	ll ret = d/(t+1);
	for(ll i = max((ll)0,h-5); i<=h+5; i++){
		if(t>=i) continue;
		ret = min(ret,i-t+d/(i+1));
	}
	return ret;
}
ll dist[100005];
void dijkstra(int start){
	for(int i=1; i<=n; i++) dist[i] = INT64_MAX;
	dist[start] = 0;
	priority_queue<pi,vector<pi>,greater<pi> >pq;
	pq.push(pi(dist[start],start));
	while(!pq.empty()){
		int cur = pq.top().second;
		ll d = pq.top().first;
		pq.pop();
		if(dist[cur]<d) continue;
		if(cur==n) continue;
		for(edge e : graph[cur]){
			int nxt = e.b;
			ll cc = e.c;
			ll dd = e.d;
			ll w = ternary(d,dd);
			if(dist[nxt]>d+w+cc){
				dist[nxt] = d+w+cc;
				pq.push(pi(dist[nxt],nxt));
			}
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int m; cin>>n>>m;
	for(int i=0; i<m; i++){
		ll a,b,c,d;
		cin>>a>>b>>c>>d;
		graph[a].push_back((edge){b,c,d});
		graph[b].push_back((edge){a,c,d});
		g[a].push_back(b); g[b].push_back(a);
	}
	dfs(1);	
	if(!v[n]){
		cout<<-1;
		return 0;
	}
	dijkstra(1);
	cout<<dist[n];
}
#ifdef MY_LOCAL
#define MY_NAMESPACE(ns) namespace ns {
#define MY_NAMESPACE_    }
#define MY_DEBUG(s)      s
#define MY_IS_DEBUG      (true)
#else
#define MY_NAMESPACE(ns) 
#define MY_NAMESPACE_    
#define MY_DEBUG(s)
#define MY_IS_DEBUG      (false)
#endif

#include <algorithm>
#include <bitset>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;

constexpr int IMIN = numeric_limits<int>::min();
constexpr int IMAX = numeric_limits<int>::max();
constexpr ll LLMIN = numeric_limits<ll>::min();
constexpr ll LLMAX = numeric_limits<ll>::max();

#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, a, b) for (int i = a; i >= b; i--)
#define fore(i, a) for (auto& i: a)
#define all(x) (x).begin(), (x).end()

template <typename T> bool chmax(T& maxval, T const& newval) { if (newval > maxval) { maxval = newval; return true; } return false; }
template <typename T> bool chmin(T& minval, T const& newval) { if (newval < minval) { minval = newval; return true; } return false; }


MY_NAMESPACE(testbed)
int main()
{
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int n, m;
	cin >> n >> m;
	vector<vector<tuple<int, ll, ll>>> e(n);
	rep(i, 0, m)
	{
		int a, b;
		ll c, d;
		cin >> a >> b >> c >> d;
		a--;
		b--;
		e[a].push_back({ b, c, d });
		e[b].push_back({ a, c, d });
	}

	auto priority_fn = [](pil const& lhs, pil const& rhs)->bool  // return true to prioritize rhs
	{
		return (rhs.second < lhs.second);
	};

	vector<ll> min_time(n, LLMAX);
	priority_queue<pil, vector<pil>, decltype(priority_fn)> q(priority_fn);
	q.push({ 0, 0 });
	min_time[0] = 0;
	while (!q.empty())
	{
		int this_city;
		ll this_time;
		tie(this_city, this_time) = q.top();
		q.pop();

		if (this_time > min_time[this_city])
			continue;

		fore(edge, e[this_city])
		{
			int next_city = get<0>(edge);
			ll cval = get<1>(edge);
			ll dval = get<2>(edge);

			ll next_time = this_time;
			if (dval == 0)
			{
				next_time += cval;
			}
			else
			{
				ll min_move = LLMAX;
				ll wait_time = max((ll)sqrt((double)dval) - 1LL - this_time, 0LL);
				for (ll adj = -2; adj <= 2; adj++)
				{
					ll this_wait_time = max(wait_time + adj, 0LL);
					ll this_move = this_wait_time + cval + dval / (this_time + this_wait_time + 1LL);
					chmin(min_move, this_move);
				}
				next_time += min_move;
			}
			if (chmin(min_time[next_city], next_time))
			{
				q.push({ next_city, next_time });
			}
		}
	}

	ll ans = min_time[n - 1];
	if (ans == LLMAX)
		ans = -1;
	cout << ans << "\n";
	return 0;
}
MY_NAMESPACE_