#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

struct Edge {
	int a, b, cost;

	Edge() {}
	
	Edge(int a, int b, int cost) {
		this->a = a;
		this->b = b;
		this->cost = cost;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

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

	#define cin f
	#define cout g

	int n, m;
	cin >> n >> m;

	vector<Edge> edges;

	for (int i = 0; i < m; ++i) {
		int a, b, cost;
		cin >> a >> b >> cost;
		--a; --b;

		edges.push_back(Edge(a, b, cost));
	}

	const int INF = int(1e9);
	vector<int> dist(n, INF);

	int source = 0;
	dist[source] = 0;

	bool redo = true;

	for (int i = 0; i < n && redo; ++i) {
		redo = false;
		for (Edge edge : edges) {
			if (dist[edge.a] + edge.cost < dist[edge.b]) {
				if (i == n - 1) {
					cout << "Ciclu negativ!\n";
					return 0;
				}

				dist[edge.b] = dist[edge.a] + edge.cost;
				redo = true;
			}
		}
	}

	for (int i = 1; i < n; ++i)
		cout << dist[i] << " ";

	//system("pause");

	return 0;
}