#include <bits/stdc++.h>
#define ll long long
//#define cin fin
//#define cout fout
using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n, m;
vector <pair <int, int> > edges[50004];
int minCost[50004];

bool bellmanFord(int startPoint) {
	queue <int> nodesToVisit;
	for (int i = 1; i <= n; i++) {
		minCost[i] = 1e7;
		nodesToVisit.push(i);
	}
	minCost[startPoint] = 0;

	for (int i = 1; i < n; i++) {
		queue <int> nodesLeft;
		while (!nodesToVisit.empty()) {
			int currNode = nodesToVisit.front();
			nodesToVisit.pop();

			for (pair <int, int> nextNode : edges[currNode])
				if (minCost[currNode] + nextNode.second < minCost[nextNode.first]) {
					minCost[nextNode.first] = minCost[currNode] + nextNode.second;
					nodesLeft.push(nextNode.first);
				}
		}

		while (!nodesLeft.empty()) {
			nodesToVisit.push(nodesLeft.front());
			nodesLeft.pop();
		}
	}

	while (!nodesToVisit.empty()) {
		int currNode = nodesToVisit.front();
		nodesToVisit.pop();

		for (pair <int, int> nextNode : edges[currNode])
			if (minCost[currNode] + nextNode.second < minCost[nextNode.first])
				return false;
	}

	return true;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v, cost;

		cin >> u >> v >> cost;
		edges[u].push_back(make_pair(v, cost));
	}
	
	if (!bellmanFord(1))
		cout << "Ciclu negativ!";
	else
		for (int i = 2; i <= n; i++) 
			cout << minCost[i] << ' ';

	return 0;
}