UOJ #32.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>

#define X first
#define Y second
#define mp std::make_pair
#define pb push_back
#define MAX_N 110
#define inf ((ll)0x3f3f3f3f3f3f3f3f)

typedef long long ll;
typedef std::pair<ll, ll> pll;

template <typename T> T chkmn(T &a, T b){
	return (a = (a > b ? b : a));
}

template <typename T> T chkmx(T &a, T b){
	return (a = (a < b ? b : a));
}

struct Edge *head[MAX_N];
struct Edge{
	int to, w, s;
	Edge *ne;
	Edge(int x, int y, int w, int s) : ne(head[x]), to(y), w(w), s(s){}
};
int n, m;
ll f[MAX_N][MAX_N][2*MAX_N];
bool fl[MAX_N][MAX_N];

std::vector<pll> vec[MAX_N];

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1, x, y, w, s; i <= m; i++){
		scanf("%d%d%d%d", &x, &y, &w, &s);
		head[x] = new Edge(x, y, w, s);
		fl[x][y] = true;
	}
	
	for(int k = 1; k <= n; k++)
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
				fl[i][j] |= fl[i][k] & fl[k][j];
	
	memset(f, 0x3f, sizeof(f));
	f[0][1][n] = 0;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			for(int k = 0; k <= 2*n; k++) if(f[i-1][j][k] < inf){
				chkmn(f[i][j][k], f[i-1][j][k]);
				for(Edge *e = head[j]; e; e = e->ne) if(k + e->s >= 0)
					chkmn(f[i][e->to][k + e->s], f[i-1][j][k] + e->w);
			}
				
	for(int i = 1; i <= n; i++)
		for(int j = 0; j <= 2 * n; j++) if(f[n][i][j] < inf){
			ll mx = inf, mn = -inf - 1;
			for(int k = 0; k <= 2 * n; k++) if(f[n - 1][i][k] < inf){
				double C = f[n][i][j] - f[n - 1][i][k];
				if(k == j){
					if(f[n][i][j] >= f[n-1][i][k])
						mn = inf, mx = -inf;
				}else if(k < j)
					chkmn(mx, (ll)ceil(C / (k - j)));
				else if(k > j)
					chkmx(mn, (ll)floor(C / (k - j)));
			}
			if(mn < mx - 1)
				vec[i].pb(mp(mn + 1, mx));
		}
		
	for(int i = 1; i <= n; i++){
		std::vector<pll> all; all.clear();
		for(int j = 1; j <= n; j++)	if(fl[1][j] & fl[j][i])
			for(auto k: vec[j])
				all.pb(k);
		auto cmp = [](pll x, pll y){
			return x.X == y.X ? x.Y < y.Y : x.X < y.X;
		};
		std::sort(all.begin(), all.end(), cmp);
		ll ans = 0, lst = -inf;
		for(auto j: all){
			if(j.X > lst) ans += j.X - lst; 
			lst = std::max(lst, j.Y);
		}
		ans += inf - lst;
		printf("%lld\n", ans > (1e18) ? -1 : ans);
	}
	return 0;
}