#include<cstdio>
#include<queue>
#include<utility>
#include<vector>
#include<cmath>

using namespace std;

int n, m;
vector<pair<int, pair<int, int>>> v[100005];
long long dis[100005];
priority_queue<pair<long long, int>> pq;

int main() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    int a, b, c, d;
    scanf("%d %d %d %d", &a, &b, &c, &d);
    v[a].push_back({b, {c, d}});
    v[b].push_back({a, {c, d}});
  }
  for (int i = 2; i <= n; i++) {
    dis[i] = 1e18;
  }
  pq.push({-dis[1], 1});
  while (!pq.empty()) {
    auto p = pq.top();
    pq.pop();
    int u = p.second;
    if (p.first != -dis[u]) {
      continue;
    }
    for (auto x: v[u]) {
      int w = x.first;
      int c = x.second.first;
      int d = x.second.second;
      int t = max(0., floor(sqrt(d) - dis[u] - 1));
      if (1 + d / (dis[u] + t + 2) < d / (dis[u] + t + 1)) {
        t++;
      }
      if (dis[w] > dis[u] + t + c + d / (dis[u] + t + 1)) {
        dis[w] = dis[u] + t + c + d / (dis[u] + t + 1);
        pq.push({-dis[w], w});
      }
    }
  }
  if (dis[n] == 1e18) {
    printf("-1\n");
  } else {
    printf("%lld\n", dis[n]);
  }
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi 3.141592653589793238
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define zip(i,a,b) for(int i=a;i<b;i++)
#define rzip(i,a,b) for(int i=a;i>=b;i--)
#define ll unsigned int
#define test int t;cin>>t; while(t--)
#define en '\n'
typedef pair<int, int>     pii;
typedef pair<char, int>    pci;
typedef pair<char, char>   pcc;
typedef vector<pii>       vii;
typedef long double ld;
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define sz(x) (int)x.size()
#define INF (1e18+5)
#define inf (1e9+5)
#define mod 1000000007


void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
// You should only debug a pair of simple data types. For example,
// the debug won't work if one of pair's elements is collection type
// (std::vector, std::map, std::set...).
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif


// bool check_prime(int n)  return whether a number is prime or not O(sqrt(N));
// int BE(int x,int n,int m)  return x^n%m; O(logN);
// void sieve()  from number 1-1000001 saare prime store kar lega  in bool is_prime[1000001] array
// vector<int> z_array(string s)  return vector which is Z-array of string s;
// vector<int> lps(string s)      return vector which is lps array of string s;
// int power(int x,int n) return x^n; O(logN);
// using_ordered_set (template for using ordered set , replace first 2 lines of this page with this code..);
const int gf = 1e6 + 9;
int dis[gf];
vector<pair<int, pii>> adj[gf];

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(0);
#ifndef ONLINE_JUDGE
	if (fopen("input.txt", "r"))
	{
		freopen ("input.txt" , "r" , stdin);
		freopen ("output.txt" , "w" , stdout);
	}
#endif
	//_______________________________-code starts-_______________________________________________

	int n, m;
	cin >> n >> m;
	zip(i, 0, m)
	{
		int a, b, t, k;
		cin >> a >> b >> t >> k;
		adj[a].pb({b, {t, k}});
		adj[b].pb({a, {t, k}});
	}
	set<pii>s;
	rep(i, 0, gf - 1)dis[i] = INF;
	dis[1] = 0;
	s.insert({0ll, 1});
	while (sz(s))
	{
		pii temp = *s.begin();
		s.erase(temp);
		int u = temp.ss;
		for (auto x : adj[u])
		{
			int v = x.ff;
			int t = temp.ff;
			int lol = sqrt(x.ss.ss);
			int var = max(0ll, lol - t - 1ll);
			vi a;
			a.pb(var); a.pb(var + 1); a.pb(var + 2);
			if (var >= 1)
				a.pb(var - 1);


			int wt = min(max(0ll, x.ss.ss - t) + x.ss.ff, x.ss.ff + x.ss.ss / (t + 1));
			zip(i, 0, sz(a))
			{
				wt = min(wt, x.ss.ff + a[i] + x.ss.ss / (a[i] + t + 1));
			}
			debug(wt);
			if (dis[v] > wt + t)
			{
				if (dis[v] != INF)
					s.erase({dis[v], v});
				dis[v] = wt + t;
				s.insert({dis[v], v});
			}
		}
	}
	if (dis[n] == INF)
		cout << -1 << en;
	else
		cout << dis[n] << en;



	return 0;
}


