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

struct edge{
  long long v;
  long long c;
  long long d;
};

long long f(long long x, long long y){
  long long l = x, r = y+1;
  while(l<r){
    long long m1 = (r-l+1)/3 + l, m2 = (r-l+1)*2/3 + l;
    long long c1 = y/(m1+1) + m1 - x, c2 = y/(m2+1) + m2 - x;
    if(c1<c2) r = m2 - 1;
    else if(c1>c2) l = m1 + 1;
    else{
      for(int i=1;;i++){
        if(m1-i<l && m2+i>r){
          l = m1;
          r = m2;
          if(l+1==r) return c1;
          break;
        }
        if(m1-i>=l){
          long long c = y/(m1-i+1) + m1-i - x;
          if(c>c1){
            l = m1;
            break;
          }
          if(c<c1){
            r = m1-1;
            break;
          }
        }
        if(m2+i<=r){
          long long c = y/(m2+i+1) + m2+i - x;
          if(c>c1){
            r = m2;
            break;
          }
          if(c<c1){
            l = m2+1;
            break;
          }
        }
      }
    }
  }
  return y/(l+1) + l - x;
}

int main(){
  long long N,M;
  cin >> N >> M;
  vector<vector<edge>> G(N,vector<edge>(0));
  for(int i=0;i<M;i++){
    long long a,b,c,d;
    cin >> a >> b >> c >> d;
    a--;
    b--;
    edge e1 = {b,c,d}, e2 = {a,c,d};
    G[a].push_back(e1);
    G[b].push_back(e2);
  }
  
  vector<long long> V(N,-1);
  priority_queue<pair<long long,long long>> Q;
  Q.push(make_pair(0,0));
  V[0] = 0;
  while(!Q.empty()){
    auto p = Q.top();
    Q.pop();
    long long t = -p.first, u = p.second;
    if(t!=V[u]) continue;
    for(int i=0;i<G[u].size();i++){
      edge e = G[u][i];
      long long cost = e.c;
      if(e.d>=t+1) cost += f(t,e.d);
      if(V[e.v]==-1 || V[e.v]>V[u]+cost){
        V[e.v] = V[u] + cost;
        Q.push(make_pair(-V[e.v],e.v));
      }
    }
  }
  
  cout << V[N-1] << endl;
  return 0;
}

/*input

*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <iomanip>
#include <climits>
#define mod 1000000007

// templates
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define sz(x) (int)x.size()
#define po(x,y)   fixed<<setprecision(y)<<x
#define ss(s) scanf(" %[^\n]%*c", s)
#define ps(s) printf("%s\n",s)
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;

void sc(int&n) {int number; scanf("%d", &number); n = number;}
void sc(ll&n) {ll number; scanf("%lld", &number); n = number;}
void _print(ll t) {printf("%lld", t);}
void _print(int t) {printf("%d", t);}
void _print(string t) {cout << t;}
void _print(char t) {printf("%c\n", t);}
void _print(lld t) {cout << t;}
void _print(double t) {cout << t;}
void _print(ull t) {cout << t;}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cout << "{"; _print(p.F); cout << ","; _print(p.S); cout << "}";}
template <class T> void _print(vector <T> v) {cout << "vec->[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T> void _print(set <T> v) {cout << "set->[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T> void _print(multiset <T> v) {cout << "multiset->[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T, class V> void _print(map <T, V> v) {cout << "map->[ "; for (auto i : v) {_print(i); cout << " ";} cout << "]";}

const ll inf = (ll)1e17 + 10;
const int N = (int)1e5 + 10;
vector<array<ll, 3>>adj[N];

void bfs(int n) {

	vector<ll>dist(n + 1, 0);
	for (int i = 0; i <= n; ++i)
	{
		dist[i] = inf;
	}
	set<array<ll, 2>>pq;
	dist[0] = 0;
	pq.insert({0, 0});
	while (!pq.empty()) {

		auto [t, node] = *pq.begin();
		pq.erase(pq.begin());
		for (auto c : adj[node]) {
			ll cost = 0;
			ll sq = 0;
			cost = t + c[1] + (c[2] / (t + 1));
			sq = sqrt(c[2]);
			if (sq * sq != c[2])sq++;
			sq--;
			if (t < sq) {
				cost = min(cost, sq + c[1] + (c[2] / (sq + 1)));
			}
			if (dist[c[0]] > cost) {
				pq.erase({dist[c[0]], c[0]});
				dist[c[0]] = cost;
				pq.insert({dist[c[0]], c[0]});

			}

		}
	}
	if (dist[n - 1] == inf)dist[n - 1] = -1;
	_print(dist[n - 1]);
}
void solve()
{
	int n, m;
	sc(n), sc(m);
	for (int i = 0; i < m; ++i)
	{
		ll u, v, c, d;
		sc(u), sc(v), sc(c), sc(d);
		u--, v--;
		adj[u].push_back({v, c, d});
		adj[v].push_back({u, c, d});
	}
	bfs(n);
}

int main()
{
//#ifndef ONLINE_JUDGE
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
//#endif
	int t = 1;
	// sc(t);
	while (t--) {
		solve();
	}
	return 0;

}