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

using namespace std;

long n, m, a, b, c, i, j, d[50010];
vector < long > G[50010], C[50010];

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, &b, &c);
		G[a].push_back(b);
		C[a].push_back(c);
	}
	
	fill(d + 1, d + n + 1, INF);
	d[1] = 0;
	
	for (i = 1; i <= n; ++i)
		for (j = 0; j < G[i].size(); ++j) 
			if (d[i] + C[i][j] < d[G[i][j]]) d[G[i][j]] = d[i] + C[i][j];
		
	if (d[1] < 0) printf("Ciclu negativ!");
	else for (i = 2; i <= n; ++i) printf("%ld ", d[i]);
	return 0;
}