#include<bits/stdc++.h>
#define ll long long
#define inf 1000000000
using namespace std;
ll n, m, s, ans;
ll d[200005], dis[200005], num[200005], head[200005];
bool vis[200005];
int u, v, w; int cnt;
void init() {
	memset(head, -1, sizeof(head));
	cnt = 1;
}
struct edge {
	int to, next, w;
}edge[200005];
void add(int u, int v, int w) {
	edge[cnt].to = v; edge[cnt].next = head[u]; edge[cnt].w = w;
	head[u] = cnt; cnt++;
}
struct node
{
	int u, d;
	bool operator<(const node& rhs)
		const
	{
		return d > rhs.d;
	}
};
void Dijkstra(int s)
{
	priority_queue<node> q;
	for (int i = 1; i <= n; ++i) d[i] = inf;
	memset(vis, 0, sizeof(vis));
	vis[s] = 1; 	d[s] = 0;
	q.push((node) { s, d[s] });
	while (!q.empty())
	{
		node x = q.top();
		int u = x.u;
		q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (int i = head[u]; i != -1; i = edge[i].next)
		{
			int v = edge[i].to, w = edge[i].w;
			if (d[u] + w < d[v])
			{
				d[v] = d[u] + w;
				q.push((node) { v, d[v] });
			}
		}
	}
}
queue <int>q;
bool SPFA_pre() {
	for (int i = 1; i <= n; ++i) dis[i] = inf;
	q.push(0);
	dis[0] = 0;
	vis[0] = 1;
	while (!q.empty()) {
		int x = q.front();
		q.pop(); vis[x] = 0;
		for (int i = head[x]; i != -1; i = edge[i].next) {
			int v = edge[i].to;
			if (dis[v] > dis[x] + edge[i].w) {
				dis[v] = dis[x] + edge[i].w;
				if (!vis[v]) {
					q.push(v);
					vis[v] = 1;
					num[v]++;
					if (num[v] > n) {
						return false;
					}
				}

			}
		}
	}return true;
}
int main() {
	cin >> n >> m; init();
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
	}
	for (int i = 1; i <= n; i++) {
		add(0, i, 0);
	}
	if (!SPFA_pre()) {
		cout << -1; return 0;
	}
	for (int j = 1; j <= n; j++) {
		for (int i = head[j]; i != -1; i = edge[i].next) {
			edge[i].w += dis[j] - dis[edge[i].to];
		}
	}
	for (int i = 1; i <= n; i++) {
		Dijkstra(i);
		ll ans = 0;
		for (int j = 1; j <= n; j++) {
			if (d[j] == inf)
				ans += j * inf;
			else
				ans += j * (d[j] + dis[j] - dis[i]);
		}cout << ans << endl;

	}
	return 0;
}