#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, ll>>> e(n);
	rep(i, 0, m)
	{
		int a, b;
		ll c, d;
		cin >> a >> b >> c >> d;
		a--;
		b--;
		ll opt = (d == 0 ? 0LL : (ll)exp(-1.0 / (double)d));
		e[a].push_back({ b, c, d, opt });
		e[b].push_back({ a, c, d, opt });
	}

	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(tpl, e[this_city])
		{
			int next_city = get<0>(tpl);
			ll cval = get<1>(tpl);
			ll dval = get<2>(tpl);
			ll optval = get<3>(tpl);

			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 = -100; adj <= 100; 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_
#include <bits/stdc++.h>
// #include <atcoder/modint>
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define INF 2000000000000000000
#define ll long long
#define ld long double
#define pll pair<ll, ll>
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

struct edge {ll to, c, d, index;};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll N, M;
  cin >> N >> M;
  vector<vector<edge>> connection(N);
  map<ll, ll> mp;
  for (ll i = 0; i < M; ++i) {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    a -= 1, b -= 1;
    connection.at(a).push_back({b, c, d, i});
    connection.at(b).push_back({a, c, d, i});
    ld l = 0, r = d;
    while (l + 0.01 < r) {
      ld m1 = (l * 2 + r) / 3.0;
      ld m2 = (l + r * 2) / 3.0;
      ld c1 = m1 + (d / (m1 + 1));
      ld c2 = m2 + (d / (m2 + 1));
      if (c1 < c2) {
        r = m2;
      }
      else {
        l = m1;
      }
    }
    ll l1 = floor(l), l2 = ceil(l);
    ll l0 = l1;
    if (l1 + d / (l1 + 1) > l2 + d / (l2 + 1)) {
      l0 = l2;
    }
    mp[i] = max(0ll, l0);
  }
  vector<ll> dist(N, INF);
  dist.at(0) = 0;
  typedef pair<ll, ll> P;// first は最短距離　second は頂点の番号
  priority_queue<P, vector<P>, greater<P>> q;
  q.push({0, 0});
  while (!q.empty()) {
    ll now = q.top().second;
    ll now_dist = q.top().first;
    q.pop();
    if (dist.at(now) < now_dist) continue;
    for (ll i = 0; i < connection.at(now).size(); ++i) {
      edge e = connection.at(now).at(i);
      ll next = e.to, c = e.c, d = e.d, index = e.index;
      if (dist.at(next) <= dist.at(now) + c) {
        continue;
      }
      ll temp = mp[index];
      // cout << temp << "\n";
      if (dist.at(now) >= temp) {
        if (dist.at(next) > dist.at(now) + c + d / (dist.at(now) + 1)) {
          chmin(dist.at(next), dist.at(now) + c + d / (dist.at(now) + 1));
          q.push({dist.at(next), next});
        }
      }
      else {
        if (dist.at(next) > temp + c + d / (temp + 1)) {
          chmin(dist.at(next), temp + c + d / (temp + 1));
          q.push({dist.at(next), next});
        }
      }
    }
  }
  if (dist.at(N - 1) == INF) {
    cout << -1 << "\n";
  }
  else {
    cout << dist.at(N - 1) << "\n";
  }
}
