#include<bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pdi pair<double, int>
#define x first
#define y second
using namespace std;
const int N = 1e2 + 10;
int f[N][N], a[N][N], n, m;
signed main() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			a[i][j] = 2e17;
	while (m--) {
		int u, v, w;
		cin >> u >> v >> w;
		a[u][v] = 0;
		a[v][u] = w;
	}
	for (int p = 1; p <= n; p++) {
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				f[i][j] = a[i][j];
		int ans = 2e18;
		for (int k = 1; k <= n; k++) {
			if (k == p) continue;
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
				}
			}
		}
		for (int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				ans = min(ans, f[i][j] + a[j][p] + a[p][i]);
			}
		}
		if (ans >= 2e17) cout << -1 << ' ';
		else cout << ans << ' ';
	}
	cout << '\n';
	return 0;
}