#include <fstream>
#include <vector>

using namespace std;

#define INF 1000000000

long x, y, c, cost[50010], n, m, i, Q[1000000], j, dex[50010], aux;
vector <long> v[50010][2];

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

	for (i = 1; i <= n; ++i) cost[i] = INF;
	cost[1] = 0;
	
	for (i = 1; i <= m; ++i) {
		f>>x>>y>>c;
		v[x][0].push_back(y);
		v[x][1].push_back(c);
	}
	
	Q[++Q[0]] = 1;
	++dex[1];
	for (i = 1; i <= Q[0]; ++i) {
		long s = v[Q[i]][0].size();
		for (j = 0; j < s; ++j) {
			if (cost[Q[i]] + v[Q[i]][1][j] < cost[v[Q[i]][0][j]]) {
				cost[v[Q[i]][0][j]] = cost[Q[i]] + v[Q[i]][1][j];
				if (dex[v[Q[i]][0][j]] < n) Q[++Q[0]] = v[Q[i]][0][j], ++dex[v[Q[i]][0][j]];
				else aux = 1;
			}
		}
	}
	
	if (aux) {
		h<<"Ciclu negativ!\n";
	} else {
		for (i = 2; i <= n; ++i) {
			h<<cost[i]<<" ";
		}
	}
		
	return 0;
}