#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], n, m, x, y, c, i, node, son, cost;
vector < pair <int, int> > G[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(make_pair(M[i].y, 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()) {
		node = Q.front();
		for (i = 0; i < G[node].size(); i++) {
			son = G[node][i].first, cost = G[node][i].second;
			if (cst[node] + cost < cst[son])
				cst[son] = cst[node] + cost;
			if (!viz[son])
				Q.push(son), viz[son] = 1;
		}
		Q.pop(), viz[node] = 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;
}