#include <stdio.h>
#include <vector>
#define INF 0x3f3f3f3f
#define H 50010

using namespace std;

long n, m, a[H], b[H], c[H], i, j, d[H], Q[H * 5];
vector < long > G[H], C[H];

int main() {
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);
	
	scanf("%ld %ld", &n, &m);
	for (i = 1; i <= m; ++i) {
		scanf("%ld %ld %ld", &a[i], &b[i], &c[i]);
		G[a[i]].push_back(b[i]);
		C[a[i]].push_back(c[i]);
	}
	
	fill(d + 2, d + n + 1, INF);
	Q[++Q[0]] = 1;
	
	for (i = 1; i <= Q[0]; ++i)
		for (j = 0; j < G[Q[i]].size(); ++j) 
			d[Q[i]] + C[Q[i]][j] < d[G[Q[i]][j]] ? d[G[Q[i]][j]] = d[Q[i]] + C[Q[i]][j], Q[++Q[0]] = G[Q[i]][j]:i;
	
	for (i = 1; i <= m; ++i) if (d[a[i]] + c[i] < d[b[i]]) {printf("Ciclu negativ!"); return 0;}
	for (i = 2; i <= n; ++i) printf("%ld ", d[i]);
	return 0;
}