#include <iostream>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <stdio.h>
#include <cstring>

#define Inf 10000

int main() {
	FILE *in = fopen("bellmanford.in", "r");
	FILE *out = fopen("bellmanford.out", "w");

	int N, M;
	fscanf(in, "%d %d", &N, &M);
	
	std::vector<std::pair<int, int> > graf[N];
	for (int i = 0; i < M; i++) {
		int x, y, c;
		fscanf(in, "%d %d %d", &x, &y, &c);
		graf[x - 1].push_back(std::make_pair(y - 1, c));
	}
	
	std::vector<int> drum(N);
	std::fill(drum.begin(), drum.end(), Inf);
	
	std::vector<int> inQueue(N);
	std::fill(inQueue.begin(), inQueue.end(), 0);
	
	std::vector<int> relaxAmount(N);
	std::fill(relaxAmount.begin(), relaxAmount.end(), 0);

	std::queue<int> qBell;
	qBell.push(0);
	inQueue[0] = 1;
	drum[0] = 0;
	
	int cycle = 0;
	
	while (!qBell.empty() && cycle == 0) {
		int n1 = qBell.front();
		qBell.pop();
		inQueue[n1] = 0;

		for (unsigned int i = 0; i < graf[n1].size(); i++) {
			std::pair<int, int> n2 = graf[n1][i];
			if (drum[n2.first] > drum[n1] + n2.second) {
				drum[n2.first] = drum[n1] + n2.second;
				if (inQueue[n2.first] == 0) {
					if (relaxAmount[n2.first] > N) {
						cycle = 1;
					} else {
						qBell.push(n2.first);
						inQueue[n2.first] = 1;
						relaxAmount[n2.first]++;
					}
				}
			}
		}
	}

	if (cycle) {
		fprintf(out, "Ciclu negativ!\n");
	} else {
		for (int i = 1; i < N; i++) {
			fprintf(out, "%d ", drum[i]);
		}
	}
	
	return 0;
}