#include <cstdio>

using namespace std;

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

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

	int arcsa[m];
	int arcsb[m];
	int weights[m];

	int dist[n+1];

	for(int i=0; i<=n; ++i)
		dist[i] = 50000000;
    dist[1] = 0;

	for(int i=0; i<m; ++i)
		scanf("%d%d%d", &arcsa[i], &arcsb[i], &weights[i]);

	for(int i=0; i<n; ++i)
		for(int j=0; j<m; ++j)
			if (dist[arcsa[j]] + weights[j] < dist[arcsb[j]])
				dist[arcsb[j]] = dist[arcsa[j]] + weights[j];

	for (int j=0; j<m; ++j)
		if (dist[arcsa[j]] + weights[j] < dist[arcsb[j]]) {
			printf("Ciclu negativ!\n");
			return 0;
		}

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