#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 3e3 + 5;
const int M = 6e3 + 5;
const int inf = 1e9;

struct edge{
	int v, w, next;
} e[M];

struct node {
	int dis, id;
	bool operator < (const node &a) const {
		return dis > a.dis;
	}
	node (int d, int x) {
		dis = d, id = x;
	}
};

int head[N], vis[N], t[N];
int n, m, cnt;
ll h[N], dis[N];

void add(int x, int y, int z) {
	e[++cnt].v = y, e[cnt].w = z, e[cnt].next = head[x], head[x] = cnt;
}

bool spfa(int start) {
	memset(vis, 0, sizeof(vis));
	memset(h, 63, sizeof(h));
	queue<int> q;
	h[start] = 1, vis[start] = 0;
	q.push(start);
	while (!q.empty()) {
		int x = q.front(); q.pop();
		vis[x] = 0;
		for (int i = head[x]; i; i = e[i].next) {
			int y = e[i].v, z = e[i].w;
			if (h[y] > h[x] + z) {
				h[y] = h[x] + z;
				if (!vis[y]) {
					vis[y] = 1, q.push(y), t[y]++;
					if (t[y] == n + 1) return false;
				}
			}
		}
	}
	return true;
}

void dijkstra(int start) {
	priority_queue<node> q;
	for (int i = 1; i <= n; i++) dis[i] = inf;
	memset(vis, 0, sizeof(vis));
	dis[start] = 0;
	q.push(node(0, start));
	while (!q.empty()) {
		int x = q.top().id; q.pop();
		if (vis[x]) continue;
		for (int i = head[x]; i; i = e[i].next) {
			int y = e[i].v, z = e[i].w;
			if (dis[y] > dis[x] + z) {
				dis[y] = dis[x] + z;
				if (!vis[y]) q.push(node(dis[y], y));
			}
		}
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		add(x, y, z);
	}
	for (int i = 1; i <= n; i++) add(0, i, 0);
	if (!spfa(0)) {
		printf("-1\n");
		return 0;
	}
	for (int i = 1; i <= n; i++)
		for (int j = head[i]; j; j = e[j].next) e[j].w += h[i] - h[e[j].v];
	for (int i = 1; i <= n; i++) {
		dijkstra(i);
		ll ans = 0;
		for (int j = 1; j <= n; j++) {
			if (dis[j] == inf) ans += j * inf;
			else ans += j * (dis[j] + h[j] - h[i]);
		}
		printf("%d\n", ans);
	}
	return 0;
}