#include <fstream>

using namespace std;

ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");

struct muchie {
	int in, out, cost;
} muchii[250005];

const int INF = 50e6;
int dist[50005];

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y, c;
		cin >> x >> y >> c;
		muchii[i] = { x, y, c };
	}
	for (int i = 2; i <= n; i++) {
		dist[i] = INF;
	}
	for (int i = 1; i <= n - 1; i++) {
		bool ok = false;
		for (int j = 1; j <= m; j++) {
			muchie& x = muchii[j];
			if (x.cost + dist[x.in] < dist[x.out]) {
				dist[x.out] = x.cost + dist[x.in];
				ok = true;
			}
		}
		if (ok == false) break;
	}
	for (int j = 1; j <= m; j++) {
		muchie& x = muchii[j];
		if (x.cost + dist[x.in] < dist[x.out]) {
			cout << "Ciclu negativ!";
			return 0;
		}
	}
	for (int i = 2; i <= n; i++) {
		cout << dist[i] << ' ';
	}
	return 0;
}