#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int NMAX = 50505;

struct edge {
	int to, cost;
};

int N, M;
vector<edge> G[NMAX];

void read() {
	scanf("%d%d", &N, &M);
	int x, y, c;
	for (int edgeIdx = 0; edgeIdx < M; edgeIdx++) {
		scanf("%d%d%d", &x, &y, &c);
		G[x].push_back({y, c});
	}
}

void solve() {
	vector<int> D(N + 1, INF);
	vector<int> cntImprovements(N + 1, 0);
	vector<bool> inQueue(N + 1, false);
	deque<int> improvedNodes;
	// add 1 
	D[1] = 0;
	improvedNodes.push_back(1);
	inQueue[1] = true;

	bool negativeCycle = false;
	while (!improvedNodes.empty() && !negativeCycle) {
		if (D[improvedNodes.back()] < D[improvedNodes.front()]) {
			int u = improvedNodes.back();
			improvedNodes.pop_back();
			improvedNodes.push_front(u);
		}

		int node = improvedNodes.front();
		improvedNodes.pop_front();
		inQueue[node] = false;

		for (auto& candidateEdge : G[node]) {
			if (D[candidateEdge.to] > D[node] + candidateEdge.cost) {
				D[candidateEdge.to] = D[node] + candidateEdge.cost;
				if (!inQueue[candidateEdge.to]) {
					improvedNodes.push_back(candidateEdge.to);
					inQueue[candidateEdge.to] = true;
					cntImprovements[candidateEdge.to]++;
					if (cntImprovements[candidateEdge.to] >= N) {
						negativeCycle = true;
					}
				}
			}
		}
	}

	if (negativeCycle) {
		printf("Ciclu negativ!\n");
	} else {
		for (int node = 2; node <= N; node++) {
			printf("%d ", D[node]);
		}
		printf("\n");
	}
}

int main() {
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);

	read();
	solve();
	return 0;
}