#include <bits/stdc++.h>
using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
#define cin f
#define cout g

int n, m;
vector<vector<pair<int, int>>> adj;
vector<int> dist, freq;
vector<bool> marked;
queue<int> q;

bool bellman_ford(int start) { 
	dist[start] = 0;
	marked[start] = true;
	q.push(start);
	bool ok = true;

	while (!q.empty() && ok) {
		int node = q.front();
		q.pop();
		marked[node] = false;

		for (auto p : adj[node]) {
			int adj_node = p.first;
			int adj_cost = p.second;

			if (dist[node] + adj_cost < dist[adj_node]) {
				dist[adj_node] = dist[node] + adj_cost;
				marked[adj_node] = true;
				freq[adj_node]++;
				q.push(adj_node);

				if (freq[adj_node] > n-1) {
					ok = false;
					break;
				}
			}
		}
	}

	return ok;
}

int main() {
	cin >> n >> m;

	dist.resize(n+1, INT_MAX);
	marked.resize(n+1, false);
	adj.resize(n+1);
	freq.resize(n+1, 0);

	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
	}

	if(bellman_ford(1)) {
		for (int i = 2; i <= n; i++)
			cout << dist[i] << " ";
	} else {
		cout << "Ciclu negativ!";
	}
	return 0;
}