#include <stdio.h>
#include <math.h>

#define INF 1000000000

long x[250010], y[250010], c[250010], cost[50010], n, m, i, viz[50010], muchie;

int main() {
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);
	
	scanf("%ld %ld", &n, &m);
	muchie = m;

	for (i = 1; i <= n; ++i) cost[i] = INF;
	cost[1] = 0;
	
	for (i = 1; i <= m; ++i) scanf("%ld %ld %ld", &x[i], &y[i], &c[i]);
	
	long h = 0;
	long aux = 1;
	while (aux && h < n + 2) {
		aux = 0;
		++h;
		for (i = 1; i <= m; ++i) {
			if (cost[x[i]] + c[i] < cost[y[i]]) {
				cost[y[i]] = cost[x[i]] + c[i];
				viz[i] = 1;
				aux = 1;
			}
		}
	}
	
	if (h == n + 2) {
		printf("Ciclu negativ!\n");
	} else {
		for (i = 2; i <= n; ++i) {
			printf("%ld ", cost[i]);
		}
	}
		
	return 0;
}