#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#include <vector>

#define db cout << t << " " << i << "----";
#define INF 1e9

using namespace std;

typedef long long LL;
typedef pair<LL, int> PLI;

const int N = 3e3 + 10, M = 6e3 + 10;

int n, m;
int e[M], w[M], ne[M], h[N], idx;
LL d[N][N], dh[N];

void add(int a, int b, int c)
{
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

bool spfa()
{
	queue<int> q;
	int cnt[N];
	bool st[N];

	memset(cnt, 0, sizeof cnt);
	memset(st, false, sizeof st);
	memset(dh, 0x3f, sizeof dh);
	dh[0] = 0, q.push(0), st[0] = true;

	while (q.size())
	{
		auto t = q.front();
		q.pop(), st[t] = false;
		for (int i = h[t]; i != -1; i = ne[i])
		{
			int j = e[i];
			if (dh[j] > dh[t] + w[i])
			{
				dh[j] = dh[t] + w[i];
				cnt[j] = cnt[t] + 1;
				if (cnt[j] >= n + 1) return true;
				if (!st[j]) q.push(j), st[j] = true;
			}
		}
	}
	return false;
}

void dijkstra(int s)
{
	priority_queue<PLI, vector<PLI>, greater<PLI>> heap;
	bool st[N];

	memset(st, false, sizeof st);
	for (int i = 1; i <= n; i++) d[s][i] = INF;
	d[s][s] = 0, heap.push({0, s});

	while (heap.size())
	{
		auto t = heap.top();
		heap.pop();

		int v = t.second;

		if (!st[v])
		{
			st[v] = true;

			for (int i = h[v]; i != -1; i = ne[i])
			{
				int j = e[i];
				if (d[s][j] > d[s][v] + w[i])
				{
					d[s][j] = d[s][v] + w[i];
					heap.push({d[s][j], j});
				}
			}
		}
	}
}

bool johnson()
{
	// 1. 加虚拟源点
	for (int i = 1; i <= n; i ++)
		add(0, i, 0);

	// 2. 跑 spfa 算法 算出 dh[0][i]
	bool res = spfa();
	if (res) return true;

	// 3. 更新边权
	for (int i = 1; i <= n; i ++)
	{
		for (int k = h[i]; k != -1; k = ne[k])
		{
			int j = e[k];
			w[k] += (dh[i] - dh[j]);
		}
	}

	// 4. 跑 n 轮 heap-Dijkstra 算法
	for (int i = 1; i <= n; i++)
		dijkstra(i);

	// 5. 恢复最短路径长度
	for (int i = 1; i <= n; i ++)
	{
		for (int j = 1; j <= n; j ++)
		{
			if (d[i][j] != INF)
				d[i][j] = d[i][j] + dh[j] - dh[i];
		}
	}

	return false;
}


int main()
{
	scanf("%d%d", &n, &m);

	memset(h, -1, sizeof h);
	for (int i = 0; i < m; i ++)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
	}

	bool res = johnson();
	if (res) puts("-1");
	else
	{
		for (int i = 1; i <= n; i ++)
		{
			LL sum = 0;
			for (int j = 1; j <= n; j ++)
				sum += (LL)j * d[i][j];
			printf("%lld\n", sum);
		}
	}

	return 0;
}