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

struct edge {
	int from, to, cost;
};

int N, M;
vector<edge> allEdges;

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);
		allEdges.push_back({x, y, c});
	}
}

void solve() {
	vector<int> D(N + 1, INF);
	D[1] = 0;
	int lastImprovedNode = 1;
	for (int step = 0; step < N && lastImprovedNode; step++) {
		lastImprovedNode = -1;
		for (auto& candidateEdge : allEdges) {
			if (D[candidateEdge.from] != INF && D[candidateEdge.to] > D[candidateEdge.from] + candidateEdge.cost) {
				lastImprovedNode = candidateEdge.to;
				D[candidateEdge.to] = D[candidateEdge.from] + candidateEdge.cost;
			}
		}
	}

	if (lastImprovedNode != -1) {
		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;
}