#include <bits/stdc++.h>

using namespace std;

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

const int INF = 1e9;
const int NMAX = 5e4;

int N, M;
bool visited[NMAX + 1];
int dist[NMAX + 1], freq[NMAX + 1];
vector<pair<int, int>> edges[NMAX + 1];
queue<int> q;

bool bf(int node0) {
	q.push(node0);
	visited[node0] = 1;
	dist[node0] = 0;

	while(!q.empty()) {
		int node = q.front();
		q.pop();

		visited[node] = 0;

		for(auto &edge: edges[node]) {
			if(dist[edge.first] > dist[node] + edge.second) {
				dist[edge.first] = dist[node] + edge.second;

				if(!visited[edge.first]) {
					q.push(edge.first);
					visited[edge.first] = 1;
				}

				if(++freq[edge.first] >= N) {
					return 0;
				}
			}
		}
	}

	return 1;
}

int main() {
	fin >> N >> M;

	for(int i = 1; i <= M; i++) {
		int x, y, c;
		fin >> x >> y >> c;

		edges[x].push_back({y, c});
	}

	// for(int i = 1; i <= N; i++) {
	// 	cout << i << " => ";
	// 	for(auto &edge: edges[i]) {
	// 		cout << "(" << edge.first << ", " << edge.second << ") ";
	// 	}
	// 	cout << '\n';
	// }

	for(int i = 1; i <= N; i++) {
		dist[i] = INF;
	}

	if(bf(1) == 0) {
		fout << "Ciclu negativ!\n";
	} else {
		for(int i = 2; i <= N; i++) {
			fout << dist[i] << " ";
		}
		fout << '\n';
	}
	return 0;
}