#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)

using namespace std;
using LL = long long;
using P = pair<LL,int>;
using vv = vector<vector<int>>;
const int INF = (int)1e9;
const LL LINF = (LL)1e18;

struct edge{
   int to;
   LL c, d;
   edge(int to, LL c, LL d): to(to), c(c), d(d) {}
};
vector<vector<edge>> G;
vector<long long> dijkstra(int N, int st){
   vector<long long> dist(N);
   for(int i = 0; i < N; i++){
	   dist[i] = LINF;
   }
   dist[st] = 0;
   priority_queue<P,vector<P>,greater<P>> q;
   q.push({dist[st], st});
   while(!q.empty()){
	   P p = q.top(); q.pop();
	   long long t = p.first;
	   int n = p.second;
	   if(dist[n] < t) continue;
	   for(auto e : G[n]){
		   int v = e.to;
		   LL c = e.c, d = e.d;
		   LL ave = sqrt(d);
		   ave = max(ave, t + 1);
		   LL cost = min(c + ave - 1 + d / ave, c + ave + d / (ave + 1));
		   if(dist[v] <= cost) continue;
		   dist[v] = cost;
		   q.push({dist[v], v});
	   }
   }
   return dist;
}

int main(){
	int N, M;
	cin >> N >> M;
	G.resize(N);
	rep(i,M){
		int a, b;
		LL c, d;
		cin >> a >> b >> c >> d;
		a--; b--;
		G[a].emplace_back(b, c, d);
		G[b].emplace_back(a, c, d);
	}
	vector<LL> dist = dijkstra(N, 0);
	LL ans = dist[N-1];
	if(ans == LINF) ans = -1;
	cout << ans << endl;

	return 0;
}

#include <bits/stdc++.h>

using namespace std;

typedef long long i64;
typedef unsigned long long ui64;
typedef vector<i64> vi;
typedef vector<vi> vvi;
typedef pair<i64, i64> pi;

#define pb push_back
#define sz(a) i64((a).size())
#define all(c) (c).begin(), (c).end()
#define REP(s, e, i) for(i=(s); i < (e); ++i)
inline void RI(i64 &i) {scanf("%lld", &(i));}
inline void RVI(vi &v) { for(i64 i=0;i<sz(v);++i) { RI(v[i]); } }
inline void RVVI(vvi &vv) { for(i64 i=0;i<sz(vv);++i) { RVI(vv[i]); } }
inline void WI(const i64 &i) {printf("%lld\n", i);}
inline void WVI(const vi &v, char sep=' ') { for(i64 i=0;i<sz(v);++i) { if(i != 0){ printf("%c", sep); } printf("%lld", v[i]);} printf("\n"); }
inline void WS(const string &s) { printf("%s\n", s.c_str()); }
inline void WB(bool b, const string &yes, const string &no) { if(b){ WS(yes);} else { WS(no);} }
inline void YESNO(bool b) { WB(b, "YES", "NO"); }
inline void YesNo(bool b) { WB(b, "Yes", "No"); }
#define BUF_LENGTH 1000000
inline void RS(string &s) {static char buf[BUF_LENGTH]; scanf("%s", buf); s = buf;}
template<typename T> inline bool IN(T &S, const typename T::key_type &key) {
  return S.find(key) != S.end();
}
template<typename T> inline bool ON(const T &b, i64 idx) {
  return ((T(1) << idx) & b) != 0;
}

i64 get_dist(i64 t_cur, i64 c, i64 d) {
  auto compute = [&](i64 t) {
    return t + c + d / (t + 1);
  };
  i64 Tmin = max(0LL, i64(floor(sqrt((long double)(d))) - 2));
  i64 Tmax = Tmin + 5;

  i64 d_min = compute(Tmin);
  i64 Topt = Tmin;
  i64 T;
  REP(Tmin, Tmax+1, T) {
    i64 d = compute(T);
    if(d < d_min) {
      d = d_min;
      Topt = T;
    }
  }

  if(t_cur <= Topt) {
    return compute(Topt) - t_cur;
  }
  return compute(t_cur) - t_cur;
}

int main(int argc, char *argv[]) {
  i64 i, j, k;
  i64 N, M; cin >> N >> M;
  using ppi = pair<i64, pi>;
  vector<vector<ppi>> edges(N);
  REP(0, M, i) {
    i64 a, b, c, d; RI(a); RI(b); RI(c); RI(d);
    --a; --b;
    edges[a].pb({b, {c, d}});
    edges[b].pb({a, {c, d}});
  }

  vi dist(N, -1);
  priority_queue<pi, vector<pi>, greater<pi>> pq;

  dist[0] = 0;
  pq.push({0, 0});
  while(!pq.empty()) {
    pi c = pq.top(); pq.pop();
    i64 cur = c.second, cur_dist = c.first;
    if(dist[cur] != cur_dist) {
      continue;
    }
    for(auto &e: edges[cur]) {
      i64 n_dist = cur_dist + get_dist(cur_dist, e.second.first, e.second.second);
      i64 n = e.first;
      if(dist[n] == -1 || n_dist < dist[n]) {
        dist[n] = n_dist;
        pq.push({n_dist, n});
      }
    }
  }

  WI(dist.back());


  return 0;
}

