#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N = 3e3 + 5;
int m, U[N], V[N], WX[N];
int n, dis[N][N], vis[N];
vector<int> g[N], W[N];
struct node {
	int v, d;
	bool operator < (const node &x) const { return d > x.d; }
};
inline bool SPFA(int s) {
    memset(vis, 0, sizeof(vis));
	memset(dis[s], 0x3f, sizeof(dis[s]));
	dis[s][s] = 0;
	priority_queue<node> q;
	q.push({s, 0});
	while (!q.empty()) {
		int u = q.top().v; q.pop();
		for (int l = 0; l < g[u].size(); ++l) {
			int i = g[u][l], w = W[u][l];
			if (dis[s][i] > dis[s][u] + w) {
				dis[s][i] = dis[s][u] + w;
				if (++vis[i] > n) return 1;
				q.push({i, dis[s][i]});
			}
		}
	}
	return 0;
}
inline void dij(int s) {
    memset(vis, 0, sizeof(vis));
	memset(dis[s], 0x3f, sizeof(dis[s]));
	dis[s][s] = 0;
	priority_queue<node> q;
	q.push({s, 0});
	while (!q.empty()) {
		int u = q.top().v; q.pop();
		if (vis[u])	continue;
		vis[u] = 1;
		for (int l = 0; l < g[u].size(); ++l) {
			int i = g[u][l], w = W[u][l];
			if (dis[s][i] > dis[s][u] + w) {
				dis[s][i] = dis[s][u] + w;
				if (!vis[i])
					q.push({i, dis[s][i]});
			}
		}
	}
	return;
}
signed main() {
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		U[i] = u, V[i] = v, WX[i] = w;
		g[u].emplace_back(v);
		W[u].emplace_back(w);
//		g[v].emplace_back(u);
//		W[v].emplace_back(w);
	}
	int root = 0;
	for (int i = 1; i <= n; ++i) {
		g[root].emplace_back(i);
		W[root].emplace_back(0);
	}
	if (SPFA(root)) {
		cout << -1;
		return 0;
	}
	for (int i = 0; i <= n; ++i)
		g[i].clear(), W[i].clear();
	for (int i = 1; i <= m; ++i) {
		int u = U[i], v = V[i], w = WX[i];
		w = w + dis[root][u] - dis[root][v];
		g[u].emplace_back(v);
		W[u].emplace_back(w);
//		g[v].emplace_back(u);
//		W[v].emplace_back(w);
	}
// 	for (int i = 1; i <= n; ++i) {
// 		cerr << i << '\n';
// 		for (int j = 0; j < g[i].size(); ++j)
// 			cerr << g[i][j] << ' ' << W[i][j] << '\n';
// 	}
	for (int i = 1; i <= n; ++i) {
		dij(i);
		int ans = 0;
		for (int j = 1; j <= n; ++j)
			if (dis[i][j] != 0x3f3f3f3f3f3f3f3f)
				ans += j * dis[i][j];
			else	ans += j * 1000000000;
		cout << ans << '\n';
	}
	return 0;
}