#include <bits/stdc++.h>
#define clog(x) std::clog << (#x) << " is " << (x) << '\n';
using LL = long long;

const int N = 2002;
struct Edge {
	int to;
	LL c, d;
	Edge(int x, LL y, LL z) : to(x), c(y), d(z) {}
};
const LL INF = 1e18;
int main() {
	//freopen("in", "r", stdin);
	std::cin.tie(nullptr)->sync_with_stdio(false);
	int cas = 1;
	// std::cin >> cas;
	while (cas--) {
		int n, m;
		std::cin >> n >> m;
		std::vector<std::vector<Edge>> e(n);
		for (int i = 0, u, v; i < m; ++i) {
			LL c, d;
			std::cin >> u >> v >> c >> d;
			if (--u == --v) continue;
			e[u].emplace_back(v, c, d);
			e[v].emplace_back(u, c, d);
		}
		auto f = [&](LL c, LL d, LL t) -> LL {
			int sn = std::sqrt(d);
			if (t > sn) return c + t + d / (t + 1);
			return c + sn + d / (sn + 1);
		};
		std::vector<LL> dist(n, INF);
		dist[0] = 0;
		std::priority_queue<std::pair<LL, int>> Q;
		Q.push({0, 0});
		while (!Q.empty()) {
			auto [du, u] = Q.top();
			Q.pop();
			if (du != -dist[u]) continue;
			for (auto [v, c, d] : e[u]) {
				LL now = f(c, d, -du);
				if (dist[v] > now) {
					dist[v] = now;
					Q.push({-now, v});
				}
			}
		}
		std::cout << (dist[n - 1] == INF ? -1 : dist[n - 1]) << '\n';
	}
	return 0;
}
#include<bits/stdc++.h>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;
typedef long long int lli;
typedef vector<int> vi;
typedef vector<long long int> vlli;
typedef pair<int,int> pii;
typedef pair<long long int,long long int> plli;
typedef vector< vi > vvi ;
typedef vector< vlli > vvlli  ;
#define fi(i,a,b) for(int i=a;i<=b;i++)
#define flli(i,a,b) for(long long int i=a;i<=b;i++)
#define bi(i,a,b) for(int i=a;i>=b;i--)
#define blli(i,a,b) for(long long int i=a;i>=b;i--)
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define all(x) x.begin(),x.end()
#define sz(x) x.size()
#define pi 2*acos(0.0)
#define pb push_back
#define tr(v,it) for(decltype(v.begin()) it=v.begin();it!=v.end();it++)
#define present(v,num) (v.find(num)!=v.end())
#define cpresent(v,num) (find(v.begin(),v.end(),num)!=v.end())
#define pq priority_queue
#define mp make_pair
const int inf=INT_MAX;
const lli INF =LLONG_MAX;
const lli mod = 1e9+7;
lli ternarysearch(lli currt,lli di)
{
	lli var=sqrt(di);
	currt=max(var,currt);
	return currt;
	lli l=currt,r=di;
	while(r-l>3)
	{
		lli mid1=l+(r-l)/3;
		lli mid2=r-(r-l)/3;
		lli val1=di/(mid1+1)+mid1;
		lli val2=di/(mid2+1)+mid2;
		if(val1<val2)
		{
			r=mid2;
		}
		else if(val1>val2)
		{
			l=mid1;
		}
		else
		{
			l=mid1;
			r=mid2;
		}
	}
	lli mini=INF;
	lli finalt=currt;
	flli(i,l,r)
	{
		lli val=di/(i+1)+i;
		if(val<mini)
		{
			mini=val;
			finalt=i;
		}
	}
	return finalt;
}
int main() {
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    fast;
    lli n,m;cin>>n>>m;
    vector<plli> costs(m);
    vector<vector<plli> > graph(n);
    flli(i,0,m-1)
    {
    	lli ui,vi;cin>>ui>>vi;
    	ui--;
    	vi--;
    	graph[ui].pb(mp(vi,i));
    	graph[vi].pb(mp(ui,i));
    	cin>>costs[i].first>>costs[i].second;
    }
    vlli finalcosts(n,INF);
	finalcosts[0]=0;
	priority_queue<plli,vector<plli>,greater<plli> > q;
	q.push(mp(0,0));
	while(!q.empty())
	{
		plli topi=q.top();
		q.pop();
		if(finalcosts[topi.second]!=topi.first)continue;
		tr(graph[topi.second],it)
		{
			lli opttime=ternarysearch(topi.first,costs[it->second].second);
			lli currcost=costs[it->second].first+(costs[it->second].second/(opttime+1))+opttime;
			if(finalcosts[it->first]>currcost)
			{
				finalcosts[it->first]=currcost;
				q.push(mp(finalcosts[it->first],it->first));
			}
		}
	}
	if(finalcosts[n-1]==INF)
	{
		cout<<-1;
	}
	else cout<<finalcosts[n-1];
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
    return 0;
}