#include <fstream>

using namespace std;

#define INF 1000000000

long x[250010], y[250010], c[250010], cost[50010], n, m, i, muchie;

int main() {
	ifstream f("bellmanford.in");
	ofstream h("bellmanford.out");
	
	f>>n>>m;
	muchie = m;

	for (i = 1; i <= n; ++i) cost[i] = INF;
	cost[1] = 0;
	
	for (i = 1; i <= m; ++i) f>>x[i]>>y[i]>>c[i];
	
	long H = 0;
	long aux = 1;
	while (aux && H < n + 2) {
		aux = 0;
		++H;
		for (i = 1; i <= m; ++i) {
			if (cost[x[i]] + c[i] < cost[y[i]]) {
				cost[y[i]] = cost[x[i]] + c[i];
				aux = 1;
			}
		}
	}
	
	if (H >= n + 2) {
		h<<"Ciclu negativ!\n";
	} else {
		for (i = 2; i <= n; ++i) {
			h<<cost[i]<<" ";
		}
	}
		
	return 0;
}