#include <iostream>
#include <fstream>
constexpr auto INF = 1000000;

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct muchie {
	int start;
	int end;
	int val;
};

int distante[50001];
muchie muchii[250001];

int main()
{
	int n, m, i, j, val;
	fin >> n >> m;
	for (int k = 1; k <= m; k++) {
		fin >> i >> j >> val;
		muchii[k].start = i;
		muchii[k].end = j;
		muchii[k].val = val;
	}
	distante[1] = 0;
	for (i = 2; i <= n; i++) {
		distante[i] = INF;
	}
	for (int itr = 1; itr <= n - 1; itr++) {
		for (int k = 1; k <= m; k++) {
			i = muchii[k].start;
			j = muchii[k].end;
			val = muchii[k].val;

			if (distante[j] > distante[i] + val)
				distante[j] = distante[i] + val;
		}
	}
	for (int k = 1; k <= m; k++) {
		i = muchii[k].start;
		j = muchii[k].end;
		val = muchii[k].val;

		if (distante[j] > distante[i] + val) {
			fout << "Ciclu negativ!";
			return 0;
		}
	}
	for (int k = 2; k <= n; k++)
		fout << distante[k] << " ";
	return 0;
}