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

#define NMAX 50005
#define INF 0x7F7F7F7F

int main()
{
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);

	int n, m;
	vector<pair<int, int>> G[NMAX];

	scanf("%d%d", &n, &m);

	for (int i = 1, x, y, c; i <= m; ++i) {
		scanf("%d%d%d", &x, &y, &c);
		G[x].push_back({y, c});
	}

	int dist[NMAX];

	memset(dist, 0x7F, sizeof(dist));
	dist[1] = 0;

	for (int k = 1, updated = 1; k <= n && updated; ++k) {
		updated = 0;
		for (int i = 1; i <= n; ++i)
			for (const auto &[neigh, cost] : G[i])
				if (dist[i] + cost < dist[neigh]) {
					dist[neigh] = dist[i] + cost;
					updated = 1;
				}

		for (int i = 1; i <= n; ++i)
			for (const auto &[neigh, cost] : G[i])
				if (dist[i] + cost < dist[neigh]) {
					puts("Ciclu negativ!");
					return 0;
				}
	}

	for (int i = 2; i <= n; ++i)
		printf("%d ", dist[i]);
	puts("");
}