#include <bits/stdc++.h>
// clang-format off
using namespace std; using ll=long long; using ull=unsigned long long; using pll=pair<ll,ll>; const ll INF=4e18;
void print0(){}; template<typename H,typename... T> void print0(H h,T... t){cout<<h;print0(t...);}
void print(){print0("\n");}; template<typename H,typename... T>void print(H h,T... t){print0(h);if(sizeof...(T)>0)print0(" ");print(t...);}
void perr0(){}; template<typename H,typename... T> void perr0(H h,T... t){cerr<<h;perr0(t...);}
void perr(){perr0("\n");}; template<typename H,typename... T>void perr(H h,T... t){perr0(h);if(sizeof...(T)>0)perr0(" ");perr(t...);}
void ioinit() { cout << fixed << setprecision(2); cerr<<fixed<<setprecision(6); ios_base::sync_with_stdio(0); cin.tie(0); }
// clang-format on

using ld=long double;
struct edge {
    int v;
    ll cost;
};
struct edg2 {
    int v;
    ll c;
    ll d;
};
class greater_cost {
   public:
    bool operator()(const edge& lh, const edge& rh) const {
        return lh.cost > rh.cost;
    }
};
using pq_mincost = priority_queue<edge, vector<edge>, greater_cost>;

const ll LG = 1e17;
vector<vector<edge>> edgcost;
vector<vector<edg2>> edgs;
vector<ll> c;
vector<ll> d;
ll dijkstra() {
    ll n = edgs.size();
    vector<bool> done(n, false);
    pq_mincost pq;
    pq.push({0, 0});
    while (!pq.empty()) {
        edge e = pq.top();
        pq.pop();
        ll cost = e.cost;
        int u = e.v;
        if (done[u]) continue;
        done[u] = true;

        if (u == n - 1) {
            return cost;
        }
        for (auto v : edgs[u]) {
            ld eps = 1e-2;
            ld left = -eps + cost;
            ld right = LG;
            while (right-left >= 1.0) {
                ld  t1 = (left+right) / 2;
                ld  t2 = t1 + eps;
                ld  x1 = t1 + v.c + ld(v.d) / (t1 + 1);
                ld  x2 = t2 + v.c + ld(v.d) / (t2 + 1);
                if (x1 < x2) {
                    right = t2;
                } else {
                    left = t1;
                }
            }
            ll nc = INF;
            ll lf=roundl(left-1.1);
            ll rg=roundl(right+1.1);
            lf = max(cost,lf);
            for (ll t = lf; t <= rg; t++) {
                ll x = t + v.c + v.d / (t + 1);
                nc = min(nc, x);
            }
            pq.push({v.v, nc});
        }
    }
    return -1;
}
int main() {
    // ダイクストラで三分探索(!?)
    ioinit();
    ll n, m;
    cin >> n >> m;
    edgcost.resize(n);
    edgs.resize(n);
    c.resize(m);
    d.resize(m);
    for (ll i = 0; i < m; i++) {
        ll a, b;
        cin >> a >> b >> c[i] >> d[i];
        a--;
        b--;
        edgs[a].push_back({int(b), c[i], d[i]});
        edgs[b].push_back({int(a), c[i], d[i]});
    }
    ll ans = dijkstra();
    print(ans);
}

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define rep(i,N) for(int i=0;i<(int)N;i++)
static int IN(void)
{
  int x=0,f=1,c;while(c=getchar(),c<48||c>57){if(c==45)f=-f;}
  while(c>47&&c<58){x=x*10+c-48,c=getchar();}return f*x;
}
static void OUT(long x){if(x<0){putchar('-'),x=-x;}if(x>=10){OUT(x/10);}putchar(x-x/10*10+48);}
typedef struct List{int nx,v,c,d;}edge;
int hsz=0;long minHeap[200001][2],output[2];
static void PUSH(int id,long key)
{
  int i=++hsz,j=i>>1;long sw[2];
  minHeap[i][0]=id,minHeap[i][1]=key;
  while(j)
  {
    if(minHeap[i][1]<minHeap[j][1])
    {
      sw[0]=minHeap[j][0],sw[1]=minHeap[j][1];
      minHeap[j][0]=minHeap[i][0],minHeap[j][1]=minHeap[i][1];
      minHeap[i][0]=sw[0],minHeap[i][1]=sw[1];
      i=j;j>>=1;
    }else break;
  }
}
static void POP(void)
{
  int i=1,j=i+1;long sw[2];
  output[0]=minHeap[i][0],output[1]=minHeap[i][1];
  minHeap[i][0]=minHeap[hsz][0],minHeap[i][1]=minHeap[hsz--][1];
  while(j<=hsz)
  {
    if(j<hsz&&minHeap[j^1][1]<minHeap[j][1]){j^=1;}
    if(minHeap[j][1]<minHeap[i][1])
    {
      sw[0]=minHeap[j][0],sw[1]=minHeap[j][1];
      minHeap[j][0]=minHeap[i][0],minHeap[j][1]=minHeap[i][1];
      minHeap[i][0]=sw[0],minHeap[i][1]=sw[1];
      i=j;j=i<<1;
    }else break;
  }
  return;
}
int main(void)
{
  int N=IN(),M=IN(),vis[100000],esz=0,adj[100000];
  long dist[100000];edge e[200000];
  rep(i,N){dist[i]=9e18;}
  rep(i,M)
  {
    int A=IN(),B=IN(),C=IN(),D=IN();
    e[2*i].nx=adj[A-1];adj[A-1]=2*i+1;
    e[2*i].v=B;e[2*i].c=C;e[2*i].d=D;
    e[2*i+1].nx=adj[B-1];adj[B-1]=2*i+2;
    e[2*i+1].v=A;e[2*i+1].c=C;e[2*i+1].d=D;
  }
  dist[0]=0l;
  PUSH(1,0l);
  while(hsz)
  {
    POP();
    int u=output[0]-1;long v=output[1];
    if(vis[u]){continue;}
    for(int i=adj[u];i;i=e[i-1].nx)
    {
      int c=e[i-1].c,d=e[i-1].d,to=e[i-1].v;long len=0l;
      if(d)
      {
        int x=sqrt(d)-1;
        if(d/(x+1)>1+d/(x+2)){x++;}
        if(d/(x+1)>1+d/(x+2)){x++;}
        if(v>1l*x){len=1l*c+1l*d/(v+1l);}
        else{len=1l*c+1l*x-v+1l*d/(1l*x+1l);}
      }else{len=1l*c;}
      if(dist[to-1]>v+len){dist[to-1]=v+len;PUSH(to,v+len);}
    }
    vis[u]=1; 
  }
  if(dist[N-1]==9e18){puts("-1");}else OUT(dist[N-1]);
}