#include <bits/stdc++.h>

using namespace std;

int main() {

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

	const int INF = 1e9;

	int n, m;
	in >> n >> m;

	vector<array<int, 3>> edges;
	for(int i = 1; i <= m; i++) {
		int x, y, c;
		in >> x >> y >> c;
		edges.push_back({x, y, c});
	}

	vector<int> dist(n + 1, INF);
	function<void(int)> bellman_ford = [&](int node) {
		dist[node] = 0;
		for(int i = 1; i < n; i++) {
			for(const auto &[x, y, c] : edges) {
				if(dist[x] + c < dist[y]) {
					dist[y] = dist[x] + c;
				}
			}
		}
	};

	bellman_ford(1);

	// Check for negative cycles
	for(const auto &[x, y, c] : edges) {
		if(dist[x] + c < dist[y]) {
			out << "Ciclu negativ!" << '\n';
			return 0;
		}
	}

	for(int i = 2; i <= n; i++) {
		out << dist[i] << ' ';
	}
	out << '\n';

	return 0;
}