#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,tot,head[N];
long long dis[N];
bool vis[N];
struct Star
{
	int to,nxt,c,d;
}edge[2*N];
void Lian(int x,int y,int z,int w)
{
	tot++;
	edge[tot].c=z;
	edge[tot].d=w;
	edge[tot].nxt=head[x];
	edge[tot].to=y;
	head[x]=tot;
}
struct Point
{
	long long dd;
	int p;
	bool operator<(const Point &x)const{
		return dd>x.dd;
	}
};
void dijkstra()
{
	for(int i=1;i<=n;i++) dis[i]=1e18;
	Point a;
	a.dd=0;
	a.p=1;
	dis[1]=0;
	priority_queue<Point> q;
	q.push(a);
	while(!q.empty())
	{
		a=q.top();
		q.pop();
		int x=a.p;
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=head[x];i;i=edge[i].nxt)
		{
			long long val;
			int y=edge[i].to;
			int k=sqrt(edge[i].d);
			if(dis[x]<=k) val=0ll+k+(edge[i].d/(k+1))+edge[i].c;
			else val=0ll+dis[x]+(edge[i].d/(dis[x]+1))+edge[i].c;
			if(val<dis[y])
			{
				dis[y]=val;
				a.dd=dis[y],a.p=y;
				q.push(a);
			}
		}
	}
 } 
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d); 
		Lian(a,b,c,d);
		Lian(b,a,c,d);
	}
	dijkstra();
	if(dis[n]==1e18) puts("-1");
	else printf("%lld",dis[n]);
	return 0;
}
/*  -*- coding: utf-8 -*-
 *
 * e.cc: E - Rush Hour 2
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100000;
const int MAX_M = 100000;
const long long LINF = 1LL << 62;

/* typedef */

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
typedef pair<ll,int> pli;

/* global variables */

vpii nbrs[MAX_N];
int cs[MAX_M], ds[MAX_M], mts[MAX_M];
ll ts[MAX_N];

/* subroutines */

ll edget(ll t, int ci, int di) { return t + ci + di / (t + 1); }

ll calcmint(ll t, int ei) {
  int ci = cs[ei], di = ds[ei];
  return edget(max(t, (ll)mts[ei]), ci, di);
}

/* main */

int main() {
  int n, m;
  scanf("%d%d", &n, &m);

  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d%d%d%d", &a, &b, cs + i, ds + i);
    a--, b--;
    nbrs[a].push_back(pii(b, i));
    nbrs[b].push_back(pii(a, i));
    mts[i] = round(sqrt(ds[i])) - 1;
  }

  fill(ts, ts + n, LINF);
  ts[0] = 0;

  priority_queue<pli> q;
  q.push(pli(0, 0));

  while (! q.empty()) {
    pli u = q.top(); q.pop();
    ll ut = -u.first;
    int ui = u.second;
    if (ts[ui] != ut) continue;

    if (ui == n - 1) break;

    for (auto ve: nbrs[ui]) {
      int vi = ve.first, ei = ve.second;
      ll vt = calcmint(ut, ei);
      if (ts[vi] > vt) {
	ts[vi] = vt;
	q.push(pli(-vt, vi));
      }
    }
  }

  ll gt = ts[n - 1];
  printf("%lld\n", (gt >= LINF) ? -1LL : gt);
  return 0;
}
