#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);

	drum[0] = 0;
	
	std::vector<int> inQueue(N);
	std::fill(inQueue.begin(), inQueue.end(), 0);
		
	std::queue<int> qBell;
	qBell.push(0);
	inQueue[0] = 1;
	
	while (!qBell.empty()) {
		int n1 = qBell.front();
		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) {
					qBell.push(n2.first);
					inQueue[n2.first] = 1;
				}
			}
		}
		qBell.pop();
	}

	for (int i = 0; i < N; i++) {
		for (unsigned int j = 0; j < graf[i].size(); j++) {
			std::pair<int, int> nod = graf[i][j];
			if (drum[nod.first] > drum[i] + nod.second) {
				fprintf(out, "Ciclu negativ!\n");
				return 0;
			}
		}
	}

	for (int i = 1; i < N; i++) {
		fprintf(out, "%d ", drum[i]);
	}

	return 0;
}