#include <algorithm>
#include <cassert>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <vector>

static const int IINF = 1 << 30;
static const long long LINF = 1LL << 60;
static const long long MOD = 1.0e+9 + 7;

template <typename T> std::vector<T> vectors(std::size_t n, T val) {
  return std::vector<T>(n, val);
}

template <typename T, typename... Args>
auto vectors(std::size_t n, Args... args) {
  return std::vector<decltype(vectors<T>(args...))>(n, vectors<T>(args...));
}

template <class T> inline bool chmin(T &a, const T &b) {
  return (a > b) ? a = b, true : false;
}

template <class T> inline bool chmax(T &a, const T &b) {
  return (a < b) ? a = b, true : false;
}

template <class T> inline void chadd(T &a, const T &b) {
  a += b, a %= MOD;
  // TODO minus case
}

template <class T>
std::ostream &operator<<(std::ostream &stream, const std::vector<T> &vec) {
  for (auto val : vec) {
    if (std::is_fundamental<T>::value)
      stream << " " << val;
    else
      stream << std::endl << val;
  }
  return stream;
}

struct Edge {
  int to;
  long long C;
  long long D;
  Edge(int to, long long c, long long d) : to(to), C(c), D(d) {}
};

using Graph = std::vector<std::vector<Edge>>;

int main() {
  int N, M;
  std::cin >> N >> M;

  Graph G(N);
  for (int i = 0; i < M; ++i) {
    int a, b;
    long long c, d;
    std::cin >> a >> b >> c >> d;
    a--, b--;
    G[a].push_back(Edge(b, c, d));
    G[b].push_back(Edge(a, c, d));
  }

  std::vector<long long> dist(N, LINF);

  using qval = std::pair<long long, int>;
  std::priority_queue<qval, std::vector<qval>, std::greater<qval>> pque;

  int s = 0;
  dist[s] = 0;
  pque.push(std::make_pair(dist[s], s));

  while (!pque.empty()) {
    // 未確定のノードの中から暫定値が最小のものを取り出す
    int v = pque.top().second;
    long long d = pque.top().first;
    pque.pop();

    // dist[v] < d はゴミを意味する
    if (dist[v] < d)
      continue;

    // 選択されたノードから出ている辺を緩和する
    for (auto &e : G[v]) {
      int nv = e.to;
      long long C = e.C;
      long long D = e.D;

      // weight の計算
      long long w = LINF;
      long long val = int(std::sqrt(D)) - 1 - d;
      long long l = val - 5;
      if (l < 0)
        l = 0;
      for (int k = 0; k < 10; ++k) {
        long long x = l + k;
        long long tmp = x + C + (long long)(D / (1 + d + x));
        w = std::min(w, tmp);
      }

      if (dist[v] + w < dist[nv]) {
        dist[nv] = dist[v] + w;
        pque.push(std::make_pair(dist[nv], nv));
      }
    }
  }

  if (dist[N-1] == LINF)
    std::cout << -1 << std::endl;
  else
    std::cout << dist[N-1] << std::endl;

}

#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
#include <functional>
#include <iterator>
#include <locale>
#include <memory>
#include <stdexcept>
#include <utility>
#include <string>
#include <fstream>
#include <ios>
#include <iostream>
#include <iosfwd>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <streambuf>
#include <complex>
#include <numeric>
#include <valarray>
#include <exception>
#include <limits>
#include <new>
#include <typeinfo>
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <climits>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdlib>
#include <cstddef>
#include <cstdarg>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <cwchar>
#include <cwctype>
using namespace std;
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const double PI2 = 8.0 * atan(1.0);
using ll = long long;
using ull = unsigned long long;

#define ALL(c) (c).begin(), (c).end()
#define CLEAR(v) memset(v,0,sizeof(v))
#define MP(a,b) make_pair((a),(b))
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ABS(a) ((a)>0?(a):-(a))
template<class T> T MIN(const T& a, const T& b) { return a < b ? a : b; }
template<class T> T MAX(const T& a, const T& b) { return a > b ? a : b; }
template<class T> void MIN_UPDATE(T& a, const T& b) { if (a > b) a = b; }
template<class T> void MAX_UPDATE(T& a, const T& b) { if (a < b) a = b; }

constexpr int mo = 1000000007;
int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

struct Edge {
	int to;
	ll C, D;
};

ll Cost(ll t, ll C, ll D) {
	ll left = t;
	ll right = t + 2000000000ll;
	while (left + 2 < right) {
		ll middle_low = (left * 2 + right) / 3;
		ll cost_middle_low = middle_low + C + D / (middle_low + 1);
		ll middle_high = (left + right * 2) / 3;
		ll cost_middle_high = middle_high + C + D / (middle_high + 1);
		if (cost_middle_low < cost_middle_high) {
			right = middle_high;
		}
		else {
			left = middle_low;
		}
	}
	ll result = numeric_limits<ll>::max();
	for (ll tt = max(t, left - 500); tt <= left + 500; ++tt) {
		MIN_UPDATE(result, tt + C + D / (tt + 1));
	}
	return result;
}

int main() {
	std::ios::sync_with_stdio(false);
	int N, M;
	cin >> N >> M;
	vector<vector<Edge>> graph(N + 1);
	REP(m, M) {
		int A, B, C, D;
		cin >> A >> B >> C >> D;
		graph[A].push_back({ B, C, D });
		graph[B].push_back({ A, C, D });
	}

	// -cost, current
	priority_queue<pair<ll, int> > q;
	q.emplace(0, 1);
	vector<ll> dp(N + 1, numeric_limits<ll>::max() / 2);
	dp[1] = 0;
	while (!q.empty()) {
		ll cost = -q.top().first;
		int current = q.top().second;
		q.pop();

		if (dp[current] != cost) {
			continue;
		}

		for (auto& edge : graph[current]) {
			ll next_cost = Cost(cost, edge.C, edge.D);
			if (dp[edge.to] > next_cost) {
				dp[edge.to] = next_cost;
				q.emplace(-next_cost, edge.to);
			}
		}
	}

	if (dp[N] == numeric_limits<ll>::max() / 2) {
		cout << -1 << endl;
	}
	else {
		cout << dp[N] << endl;
	}
}
