求大佬帮帮，实在d不出来bug了QAQ

#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;

const int N = 6e3 + 10;
const int INF = 1e9;

typedef long long LL;

int n, m;

int h[N], e[N], nxt[N], w[N], idx;
LL dist[N];
bool st[N];
int cnt[N];

typedef pair<LL, int> PII;
LL dis[N];

void add(int u, int v, int wgt)
{
	e[idx] = v;
	w[idx] = wgt;
	nxt[idx] = h[u];
	h[u] = idx++;
}

inline void init()
{
	for (int i = 1; i <= n; i++) add(0, i, 0);
}

bool spfa()
{
	memset(dist, 0x3f, sizeof dist);
	dist[0] = 0;

	queue<int> q;
	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 = nxt[i])
		{
			int j = e[i];
			if (dist[j] > dist[t] + w[i])
			{
				dist[j] = dist[t] + w[i];
				cnt[j] = cnt[t] + 1;
				if (cnt[j] > n) return true;
				if (!st[j])
				{
					q.push(j);
					st[j] = true;
				}
			}
		}
	}

	return false;
}

void addw()
{
	for (int i = 1; i <= n; i++)
		for (int j = h[i]; j != -1; j = nxt[j])
			w[j] += dist[i] - dist[e[j]];
}

void dijkstra(int u)
{
	for (int i = 1; i <= n; i++) dis[i] = INF;
	memset(st, 0, sizeof st);
	dis[u] = 0;
	//priority_queue<PII, vector<PII>, greater<PII>> heap;
	priority_queue<PII> heap;
	
	heap.push({ 0, u });

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

		int ver = t.second;
		LL distance = dis[ver];

		if (st[ver]) continue;
		st[ver] = true;

		for (int i = h[ver]; i != -1; i = nxt[i])
		{
			int j = e[i];
			if (dis[j] > distance + w[i])
			{
				dis[j] = distance + w[i];
				if (!st[j]) heap.push({ -dis[j], j });
			}
		}
	}
}

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

	memset(h, -1, sizeof h);

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

	init();

	//for (int i = h[0]; i != -1; i = nxt[i]) cout << i << endl;

	if (spfa())
	{
		cout << -1 << endl;
		return 0;
	}

	//for (int i = 1; i <= n; i++) cout << i << " " << cnt[i] << endl;

	//for (int i = 1; i <= n; i++) cout << i << " " << dist[i] << endl;

	addw();

	for (int i = 1; i <= n; i++)
	{
		dijkstra(i);

		LL ans = 0;
		for (LL j = 1; j <= n; j++)
		{
			if (dis[j] == INF)
				ans += j * (LL)INF;
			else
				ans += j * (dis[j] + dist[j] - dist[i]);
		}

		printf("%lld\n", ans);
	}

	return 0;
}