#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a),i##end=(b);i<i##end;i++)
#define REP(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define RFOR(i,a,b) for(int i=(a),i##end=(b);i>i##end;i--)
#define RREP(i,a,b) for(int i=(a),i##end=(b);i>=i##end;i--)
typedef long long LL;

struct Edge{
	int from,to,add,mul;
	Edge(const int& u,const int& v,const int& a,const int& m):from(u),to(v),add(a),mul(m) {}
	LL solve(const LL& t) {
		int x=(int)sqrt(mul+0.5);
		int a=x,b=x*(x+1)>mul?x:x+1;
		//printf("a=%d b=%d\n",a,b);
		if(t<1LL*b) return a+b+add-1;
		else return t+add+mul/(t+1LL);
	}
};

struct Heapnode{
	int u; LL d;
	Heapnode(const int& u,const LL& d):u(u),d(d) {}
	bool operator < (const Heapnode& rhs) const { return d>rhs.d; }
};

struct Dijkstra{
	static const int maxn=100000+5;
	std::vector<Edge> edges;
	std::vector<int> G[maxn];
	LL dist[maxn];
	Dijkstra() {
		FOR(i,0,maxn) G[i].clear();
		edges.clear();
	}
	void AddEdge(const int& from,const int& to,const int& add,const int& mul,const int& t=-1) {
		edges.push_back(Edge(from,to,add,mul));
		G[from].push_back(t>=0?t:edges.size());
	}
	LL dijkstra(const int& s,const int& t) {
		std::priority_queue<Heapnode> Q;
		while(!Q.empty()) Q.pop();
		Q.push(Heapnode(s,0));
		memset(dist,-1,sizeof(dist));
		dist[s]=0LL;
		while(!Q.empty()) {
			Heapnode h=Q.top(); Q.pop();
			int u=h.u;
			assert(h.d>=dist[u]&&dist[u]>=0LL);
			if(dist[u]!=h.d) continue;
			if(u==t) return dist[t];
			FOR(i,0,G[u].size()) {
				Edge e=edges[G[u][i]];
				int v=e.to;
				LL ans=e.solve(dist[u]);
				if(ans<dist[v]||dist[v]<0LL) Q.push(Heapnode(v,dist[v]=ans));
			}
		}
		assert(dist[t]==-1LL);
		return -1LL;
	}
}D;

int n,m;
int main() {
	scanf("%d%d",&n,&m);
	//printf("%d %d\n",n,m);
	FOR(i,0,m) {
		int from,to,add,mul; scanf("%d%d%d%d",&from,&to,&add,&mul);
		D.AddEdge(from,to,add,mul,i<<1);
		D.AddEdge(to,from,add,mul,(i<<1)|1);
		//printf("OK!%d\n",i);
	}
	printf("%lld\n",D.dijkstra(1,n));
	return 0;
}

#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<utility>
#include<algorithm>
#include<functional>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<set>

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using piii = pair<int,pii>;

#define LL_INF 1e18+5
#define INT_INF 1e9+5
#define MOD 1e9+7

struct edge{
    ll to,cost,dis;
    edge(){};
    edge(ll t,ll c,ll d){
        to = t;
        cost = c;
        dis = d;
    };
};

ll time_calc(ll time,ll dis){
    //time+1+dis/(time+1) >= 2*root(dis) dis = (time+1)^2
    ll mintime = sqrt(dis);
    if(mintime == 0) mintime = 1;
    if(mintime+dis/mintime > mintime+1+dis/(mintime+1)){
        mintime++;
    }
    if(time < mintime){
        return mintime-1+dis/mintime;
    }
    else return time+dis/(time+1);
}


int main(){

    ll N,M; cin >> N >> M;
    vector<vector<edge> > E(N);
    for(ll i=0;i<M;i++){
        ll A,B,C,D; cin >> A >> B >> C >> D;
        A--;B--;
        E[A].push_back(edge(B,C,D));
        E[B].push_back(edge(A,C,D));
    }
    priority_queue<pll,vector<pll>,greater<pll>> q;
    q.push(pll(0,0));
    vector<ll> min_time(N,LL_INF);
    min_time[0] = 0;
    vector<bool> visited(N,false);
    while (!q.empty())
    {
        pll pos = q.top();q.pop();
        ll cur = pos.second;
        ll time = pos.first;
        if(min_time[cur] < time || visited[cur]) continue;
        visited[cur] = true;
        for(auto&next:E[cur]){
            ll ne = next.cost+time_calc(time,next.dis);
            if(min_time[next.to] > ne && !visited[next.to]){
                min_time[next.to] = ne;
                q.push(pll(ne,next.to));
            }
        }
    }

    if(min_time[N-1] < LL_INF){
        cout << min_time[N-1] << endl;
    }
    else cout << -1 << endl;
    
}
