#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>

#define pii pair<int,int>
#define INFINIT 1000000000

using namespace std;

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

int main() {

	int n, m;
	fin >> n >> m;

	vector<vector<pii>> vecini(n + 1); //vecin stocat sub forma {cost,vecin}
	
	for (int i = 1; i <= m; i++) {
		int x, y, c;
		fin >> x >> y >> c;

		vecini[x].push_back({ c,y });
	}

	//algoritmul lui bellman ford:

	//distanta de la S(1)
	vector<int> distanta(n + 1, INFINIT);
	distanta[1] = 0;

	bool cicluNegativ = false;

	for (int x = 0; x < n; x++) { // parcurgem nodurile de n-1 passuri
		bool passValid = false;
		for (int i = 0; i <= n; i++) {
			//pt fiecare nod,pe rand(i) vedem daca putem sa relaxam vecinii lui mergand  prin el + cost
			for (auto v : vecini[i]) {
				if (distanta[v.second] > distanta[i] + v.first) {
					distanta[v.second] = distanta[i] + v.first;
					passValid = true;
				}
			}
		}
		if (!passValid) break;
		if (passValid && x == n - 1) {
			cicluNegativ = true;
		}
	}
	if (cicluNegativ) fout << "Ciclu negativ! ";else
	for (int i = 2; i <= n; i++) {
		fout << distanta[i] << ' ';
	}

	return 0;
}