#include <stdio.h>
#include <iostream>
#include <vector>
#define Inf 3000

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, parent;
	for (int i = 0; i < N; i++) {
		drum.push_back(Inf);
	}

	drum[0] = 0;

	for (int k = 0; k < N - 1; k++) {
		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) {
					drum[nod.first] = drum[i] + nod.second;
				}
			}
		}
	}

	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;
}