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

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 = 1, 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);
	priority_queue<pair<int, int> , vector<pair<int, int> > , greater<pair<int, int> > > Q;
	dist[1] = 0;
	Q.push(make_pair(dist[1], 1));
	while (!Q.empty()) {
		int w = Q.top().first;
		int u = Q.top().second;
		Q.pop();
		if (dist[u] == w) {
			for (int e = eb[u]; e; e = en[e]) {
				int v = et[e], w = ew[e];
				if (dist[u] + w < dist[v]) {
					dist[v] = dist[u] + w;
					Q.push(make_pair(dist[v], v));
				}
			}
		}
	}
	bool cycle = false;
	for (int i = 1; i <= M; i++) {
		int u = ef[i], v = et[i], w = ew[i];
		if (dist[u] + w < dist[v]) {
			cycle = true;
			break;
		}
	}
	if (cycle) {
		cout << "Ciclu negativ!";
	} else {
		for (int i = 1; i <= N; i++) {
			cout << dist[i] << " ";
		}
	}
	return 0;
}