#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], freq[50004];
bitset <50004> hasToBeVisited;

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

	while (!nodesToVisit.empty()) {
		int currNode = nodesToVisit.front();
		nodesToVisit.pop();
		hasToBeVisited[currNode] = 0;

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

				freq[nextNode.first]++;
				if (freq[nextNode.first] >= n)
					return false;
				
				if (!hasToBeVisited[nextNode.first]) {
					hasToBeVisited[nextNode.first] = 1;
					nodesToVisit.push(nextNode.first);
				}
			}
	}

	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;
}