
#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// template <class c, class cmp = less<c> > using ordered_set = tree<c, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...) 
#endif
template<class T> ostream& operator<<(ostream &os, vector<T> V) {os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {return os << "(" << P.first << "," << P.second << ")";}
template <typename T,typename U>pair<T,U> operator+(const pair<T,U> & l,const std::pair<T,U> & r) { return {l.first+r.first,l.second+r.second};}
typedef long long int ll;
const ll mod =1e9+7;
const int maxn = 100002;
#define endl '\n'
#define int ll
#define ld long double
#define all(x) (x).begin(),(x).end()
vector<pair<int,int>> g[maxn];
int c[maxn], d[maxn];
vector<int> djikstra(ll src,ll n)
{	
  priority_queue< pair<int,int>, vector <pair<int,int>> , greater<pair<int,int>> > pq; 
  vector<ll> dist(n+1, 1e18),vis(n+1,0); 
  pq.push(make_pair(0, src)); 
  dist[src] = 0; 
  while (!pq.empty()) 
  { 
      ll u = pq.top().second; 
      pq.pop(); 
      if(vis[u]) continue;
      vis[u] = 1;

      for (auto i:g[u]) 
      { 
          ll v = i.first; 
          ll x = dist[u], D = d[i.second];
          ll C = c[i.second];
          ll weight = 1e15;

          int temp = sqrtl(D);
          for(int t = max(0ll, -x + temp - 2); t<=-x + temp + 2;t++){
          		weight = min(weight, C + (t + D/(x + t + 1)));
          }

          weight = min(weight, C + (0LL + D/(x + 0LL + 1)));
          


          if (dist[v] > dist[u] + weight) 
          { 
              dist[v] = dist[u] + weight; 
              pq.push(make_pair(dist[v], v)); 
          } 
      } 
  } 
  return dist;
}
int32_t main()
{ 
  IOS
  

  	int n, m;
  	cin >> n >> m;

  	for(int i = 1;i<=m;i++){
  		int a, b;
  		cin >> a >> b >> c[i] >> d[i];

  		g[a].push_back({b, i});
  		g[b].push_back({a, i});
  	}

	int ans = djikstra(1, n)[n];
	if(ans >=1e15) ans = -1;
	cout << ans << endl;




	


  
}



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

#define int long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

const int MOD=(int)1e9+7;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    //freopen("teamwork.in","r",stdin);
    //freopen("teamwork.out","w",stdout);
    int n;
    cin>>n;
    vector<pair<int,pair<int,int>>> v;
    for(int i=0;i<n;i++) {
        int a,b,c;
        cin>>a>>b>>c;
        v.push_back({a,{b,c}});
    }
    sort(all(v));
    int t=0,ans=MOD;
    for(int i=0;i<n;i++){
        t+=v[i].first-t;
        if(v[i].second.second-t>=1) ans=min(ans,v[i].second.first);
    }
    if(ans!=MOD) cout<<ans;
    else cout<<-1;
}
