#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

#define NMAX 50002
#define MMAX 250002
#define INF 1 << 30

struct muchie {
	int x, y, c;
} M[MMAX];

int cst[NMAX], viz[NMAX], viz_cnt[NMAX], n, m, x, y, c, p, i, j;
vector <int> G[NMAX], C[NMAX];
queue <int> Q;

int main() {
	
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);
	
	scanf("%d %d", &n, &m);
	for (i = 1; i <= m; i++) {
		scanf("%d %d %d", &M[i].x, &M[i].y, &M[i].c);
		G[M[i].x].push_back(M[i].y);
		C[M[i].x].push_back(M[i].c);
	}
	
	for (i = 2; i <= n; i++)
		cst[i] = INF;
	
	long long stp = 0, comp = (long long) n * (long long) m;
	Q.push(1), cst[1] = 0, viz[1] = 1;
	while (!Q.empty()) {
		p = Q.front();
		for (i = 0; i < G[p].size(); i++) {
			j = G[p][i];
			if (cst[p] + C[p][i] < cst[j])
				cst[j] = cst[p] + C[p][i];
			if (!viz[j])
				Q.push(j), viz[j] = 1;
		}
		Q.pop(), viz[p] = 0, stp++;
		if (stp > comp) break;
	}
	
	int negative_cycle = 0;
	for (i = 1; i <= m; i++)
		if (cst[M[i].x] + M[i].c < cst[M[i].y])
			negative_cycle = 1;
	
	if (negative_cycle)
		printf("Ciclu negativ!");
	else
		for (i = 2; i <= n; i++)
			printf("%d ", cst[i]);
	
	return 0;
}