#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

const int V = 50000 + 1;
const int E = 250000 + 1;
const int INF = 1 << 30;

int N, M;
int dist[V];
int ec, eb[V], ef[E], et[E], ew[E], en[E];

int main() {
	ifstream cin("bellmanford.in");
	ofstream cout("bellmanford.out");
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		ef[ec] = u;
		et[ec] = v;
		ew[ec] = w;
		en[ec] = eb[u];
		eb[u] = ec++;
	}
	fill(dist + 1, dist + 1 + N, INF);
	dist[1] = 0;
	bool cycle;
	for (int i = 0; i < N; i++) {
		cycle = false;
		for (int j = 0; j < M; j++) {
			int u = ef[j], v = et[j], w = ew[j];
			if (dist[u] + w < dist[v]) {
				dist[v] = dist[u] + w;
				cycle = true;
			}
		}
		if (!cycle) {
			break;
		}
	}
	if (cycle) {
		cout << "Ciclu negativ!";
	} else {
		for (int i = 2; i <= N; i++) {
			cout << dist[i] << " ";
		}
	}
	return 0;
}