#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

template<class T>
using nega_queue = priority_queue<T,vector<T>,greater<T>>;

ll waittime(ll D){
  ll l=0, r=40000;
  while(r-l > 1){
    ll m = (l+r)/2;
    if(m*m+m <= D) l=m; else r=m;
  }
  return l;
}

struct Edge{ int to; ll c,d,w; };

const ll INF = 1001001001001001001;

int N,M;
vector<vector<Edge>> E;

int main(){
  cin >> N >> M;
  E.resize(N);
  rep(i,M){
    int a,b,c,d; cin >> a >> b >> c >> d;
    a--; b--;
    E[a].push_back({ b,c,d,waittime(d) });
    E[b].push_back({ a,c,d,waittime(d) });
  }
  vector<ll> D(N,INF);
  nega_queue<pair<ll,int>> Q;
  D[0] = 0;
  Q.push({0ll,0});
  while(Q.size()){
    int p = Q.top().second;
    ll d = Q.top().first;
    Q.pop();
    if(D[p] != d) continue;
    for(auto e : E[p]){
      ll t = max(d,e.w);
      ll nxd = t + e.c + e.d / (t+1);
      if(D[e.to] <= nxd) continue;
      D[e.to] = nxd;
      Q.push({nxd,e.to});
    }
  }

  if(D[N-1] == INF) cout << "-1\n";
  else cout << D[N-1] << "\n";
  return 0;
}


struct ios_do_not_sync{
  ios_do_not_sync(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
  }
} ios_do_not_sync_inst;

#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
#include<numeric>
#include<array>

#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define printVec(v) printf("{"); for (const auto& i : v) { std::cout << i << ", "; } printf("}\n");
#define all(v) (v).begin(),(v).end()
#define all_rev(v) (v).rbegin(),(v).rend()
#define debug(x) cout << #x << ": " << x << '\n';
#define degreeToRadian(deg) (((deg)/360)*2*M_PI)
#define radianTodegree(rad) (((rad)/2/M_PI)*360)

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using namespace std;
using ll = long long;
using P = pair<int,int>;
using PL = pair<ll, ll>;
const ll INF = 1LL<<60;
const int MOD = 1e9 + 7;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main() {
  //cin.tie(0);ios::sync_with_stdio(false);
  //cout << fixed << setprecision(15);
  
  int n;
  cin >> n;
  vector<P> a;
  vector<P> b;

  rep (i, n) {
    int t, tt;
    cin >> t >> tt;
    a.push_back({t,i});
    b.push_back({tt,i});
  }
  sort(all(a));
  sort(all(b));

  if (a[0].second != b[0].second) {
    cout << max(a[0].first, b[0].first) << endl;
  } else {
    int t = a[0].first + b[0].first;
    int tt = max(a[1].first, b[0].first);
    int ttt = max(a[0].first, b[1].first);

    t = min(t, tt);
    t = min(t, ttt);
    cout << t << endl;
  }

  return 0;
}
