#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
inline int read() {
	int x=0,f=1;char c=getchar();
	while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
	while(c>=48&&c<=57)x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
using namespace std;
const int M=1e5+5;
typedef long long ll;
int n,m;
struct node {
	int t,c,d;
};
vector <node> E[M];
struct PR {
	int x;ll d;
	bool operator <(const PR &a)const {return d>a.d;}
};
priority_queue <PR> q;
ll dis[M];
bool vis[M];
int main() {
	n=read(),m=read();
	rep(i,1,m){
		int u=read(),v=read(),c=read(),d=read();
		E[u].push_back((node){v,c,d});
		E[v].push_back((node){u,c,d});
	}
	rep(i,1,n)dis[i]=2e18;
	dis[1]=0;
	q.push((PR){1,0});
	while(!q.empty()){
		int top=q.top().x;q.pop();
		if(vis[top])continue;
//		printf("top=%d,E=%d\n",top,E[top].size());
		vis[top]=1;
//		puts("A");
		rep(i,0,E[top].size()-1){
			int to=E[top][i].t,c=E[top][i].c,d=E[top][i].d;
//			printf("to=%d\n",to);
			ll t1=dis[top]+c+d/(dis[top]+1);
			ll x=sqrt(d);
			for(ll j=max(dis[top],x-600);j<=x+600;j++)t1=min(t1,0ll+j+c+d/(j+1));
//			printf("to=%d\n",to);
			if(dis[to]>t1)q.push((PR){to,dis[to]=t1});
		}
//		puts("B");
	}
//	puts("A");
	if(dis[n]==2e18)puts("-1");
	else printf("%lld\n",dis[n]);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define MS(a, b) memset(a, b, sizeof(a))
#define REP(a, b, c) for (register int a = b, _n = c; a <= _n; ++a)
#define DREP(a, b, c) for (register int a = b, _n = c; a >= _n; --a)
#define FOR(a, b, c) for (register int a = b, _n = c; a < _n; ++a)
#define EREP(a, b) for (register int a = head[b]; a; a = edge[a].nxt)

inline int rd() {
    int x = 0; char c = getchar(); bool f = 0;
    while (c < '0' && c != '-') c = getchar();
    if (c == '-') f = 1, c = getchar();
    while (c >= '0') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return f ? -x : x;
}

const int SIZE = 2e5 + 100;

int n; 

int head[SIZE], ecnt;
struct Edge {
	int v, nxt;
} edge[SIZE << 1];
void Add_Edge (int u, int v) {
	edge[++ecnt] = (Edge) { v, head[u] };
	head[u] = ecnt;
}

int dep[SIZE], F[SIZE];
int mx[SIZE][2];
int Len = -1, A, B;
void dfs (int u, int fa) {
	F[u] = fa;
	dep[u] = dep[fa] + 1;
	mx[u][0] = mx[u][1] = u;
	EREP (i, u) {
		int v = edge[i].v;
		if (v == fa) continue;
		dfs(v, u);
		if (dep[mx[v][0]] > dep[mx[u][0]])
			mx[u][1] = mx[u][0], mx[u][0] = mx[v][0];
		else if (dep[mx[v][0]] > dep[mx[u][1]])
			mx[u][1] = mx[v][0];
	}
	if (dep[mx[u][0]] + dep[mx[u][1]] - 2 * dep[u] > Len) {
		Len = dep[mx[u][0]] + dep[mx[u][1]] - 2 * dep[u];
		A = mx[u][0];
		B = mx[u][1];
	}
}
bool mark[SIZE];
int E;
int ans[SIZE];
void D (int u, int fa) {
	++E;
	ans[u] = E;
	EREP (i, u) {
		int v = edge[i].v;
		if (v == fa) continue;
		if (!mark[v]) D(v, u);
	}
	EREP (i, u) {
		int v = edge[i].v;
		if (v == fa) continue;
		if (mark[v]) D(v, u);
	}
	++E;
}

void _main () {
	n = rd();
	FOR (i, 1, n) {
		int u = rd(), v = rd();
		Add_Edge(u, v);
		Add_Edge(v, u);
	}
	dfs(1, 0);
	int T = A;
	while (A != B) {
		if (dep[A] < dep[B]) swap(A, B);
		mark[A] = 1;
		A = F[A];
	} mark[A] = 1;
	D(T, 0);
	REP (i, 1, n) printf ("%d ", ans[i]);
}

int main () {
#ifdef LOCAL
	freopen("in.txt", "r", stdin);
#endif
	_main();
	return 0;
}
