#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib> 
#include <ctime>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) (sort(all(v)), v.erase(unique(all(v)), v.end()))
#define setio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
//cout << fixed << setprecision(15);
typedef long long ll;
typedef pair<ll, int> p;

int N, M;
vector<int> adj[2004];
int adj2[2004][2004];
ll dist[2004];

void dijk(int s) {
	int i;
	for (i = 1; i <= N; i++) dist[i] = -1;
	dist[s] = 0;
	priority_queue<p> pq;
	pq.push({ 0,s });
	while (!pq.empty()) {
		int u = pq.top().y; ll cost = -pq.top().x;
		pq.pop();
		if (dist[u] < cost) continue;
		for (auto& v : adj[u]) {
			int c = adj2[u][v];
			if (dist[v] == -1 || dist[v] > dist[u] + c) {
				dist[v] = dist[u] + c;
				pq.push({ -dist[v],v });
			}
		}
	}
}
int main() {
	setio;
	int i, j; cin >> N >> M;
	for (i = 1; i <= N; i++) for (j = 1; j <= N; j++) adj2[i][j] = -1;

	for (i = 1; i <= M; i++) {
		int a, b, c; cin >> a >> b >> c;
		if (adj2[a][b] == -1 || adj2[a][b] > c) adj2[a][b] = c;
	}
	for (i = 1; i <= N; i++) for (j = 1; j <= N; j++) {
		if (adj2[i][j] != -1) adj[i].push_back(j);
	}
	for (i = 1; i <= N; i++) {
		dijk(i);
		ll mn;
		if (adj2[i][i] != -1) mn = adj2[i][i];
		else mn = (ll)1e10;
		for (j = 1; j <= N; j++) {
			if (i == j) continue;
			if (dist[j] == -1 || adj2[j][i] == -1) continue;
			mn = min(mn, dist[j] + adj2[j][i]);
		}
		if (mn == (ll)1e10) cout << -1 << '\n';
		else cout << mn << '\n';
	}
}
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <functional>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <bitset>
#include <math.h>
#include <random>
#include <chrono>
#include <assert.h>
using namespace std ;
using ll = long long ;
using ld = long double ;
template<class T> using V = vector<T> ;
template<class T> using VV = V<V<T>> ;
using pll = pair<ll,ll> ;
#define all(v) v.begin(),v.end()
ll mod = 1000000007 ;
long double pie = acos(-1) ;
ll INF = 1e18 ;
 
void yorn(bool a){if(a) cout << "Yes" << endl ; else cout << "No" << endl ;}
//void YorN(bool a){if(a) cout << "YES" << endl ; else cout << "NO" << endl ;}
ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
ll extGCD(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x = 1 ;
        y = 0 ;
        return a ;
    }
    ll d = extGCD(b,a%b,y,x) ;
    y -= a/b*x ;
    return d ;
}
void fix_cout(){cout << fixed << setprecision(20) ;}
template<class T> void chmax(T &a,T b){if(a<b) a = b ;}
template<class T> void chmin(T &a,T b){if(a>b) a = b ;}

int main(){
    int n,m ;
    cin >> n >> m ;
    VV<pair<int,pair<ll,ll>>> g(n) ;
    for(int i=0;i<m;i++){
        ll a,b,c,d ;
        cin >> a >> b >> c >> d ;
        a-- ; b-- ;
        g[a].emplace_back(b,make_pair(c,d)) ;
        g[b].emplace_back(a,make_pair(c,d)) ;
    }
    using T = pair<ll,int> ;
    priority_queue<T,V<T>,greater<T>> pq ;
    V<ll> dis(n,INF) ;
    pq.emplace(0,0) ;
    while(!pq.empty()){
        int cur = pq.top().second ;
        ll cost = pq.top().first ;
        pq.pop() ;
        if(dis[cur]<cost) continue ;
        dis[cur] = cost ;
        for(auto p:g[cur]){
            int nx = p.first ;
            ll c = p.second.first ;
            ll d = p.second.second ;
            if(dis[nx]!=INF) continue ;
            ll f = sqrt(d)-1 ;
            ll mn = INF ;
            if(cost<=f){
               chmin(mn,(f+c+d/(f+1)));
            }
            if(cost<=f+1){
                chmin(mn,f+1+c+d/(f+2)) ;
            }
            if(cost<=f+1){
                chmin(mn,(f+1+c+d/(f+2))) ;
            }
            chmin(mn,cost+c+d/(cost+1)) ;
            pq.emplace(mn,nx) ;
        }
    }
    if(dis[n-1]==INF) dis[n-1] = -1 ;
    cout << dis[n-1] << endl ;
}