#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];
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 + 1, d + n + 1, INF);
	d[1] = 0;
	
	for (i = 1; i <= n; ++i)
		for (j = 0; j < G[i].size(); ++j) 
			d[i]+C[i][j]<d[G[i][j]]?d[G[i][j]]=d[i]+C[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;
}