#include <fstream>
#include <queue>
#include <vector>

const int oo = 0x3f3f3f3f;

using namespace std;

vector<int> bellmanford(vector<vector<pair<int, int>>>& graph, int start) {
	queue<int> q;
	vector<int> count(graph.size());
	vector<int> distance(graph.size(), oo);
	vector<bool> in_queue(graph.size());

	q.push(start);
	in_queue[start] = true;
	distance[start] = 0;

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

		++count[node];
		if (count[node] >= graph.size()) {
			return vector<int>();
		}

		for (auto edge : graph[node]) {
			if (distance[node] + edge.second < distance[edge.first]) {
				distance[edge.first] = distance[node] + edge.second;
				if (!in_queue[edge.first]) {
					in_queue[edge.first] = true;
					q.push(edge.first);
				}
			}
		}
		in_queue[node] = false;
	}

	distance.erase(distance.begin() + start);
	distance.erase(distance.begin());
	return distance;
}

int main() {

	ifstream fin("bellmanford.in");
	ofstream fout("bellmanford.out");
	vector<vector<pair<int, int>>> graph;

	int n, m;
	fin >> n >> m;
	graph.resize(n + 1);
	for (int i = 1; i <= m; ++ i) {
		int node_a, node_b, cost;
		fin >> node_a >> node_b >> cost;
		graph[node_a].push_back({node_b, cost});
	}

	auto ans = bellmanford(graph, 1);

	if (ans.size() == 0 && n != 0) {
		fout << "Ciclu negativ!\n";
	} else {
		for (int val : ans) {
			fout << val << " ";
		}
		fout << "\n";
	}

	return 0;
}