#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 <tuple <int, int, int> > edges;
int minCost[50004];

bool bellmanFord(int startPoint) {
	for (int i = 1; i <= n; i++)
		minCost[i] = 1e7;
	minCost[startPoint] = 0;

	for (int i = 1; i < n; i++)
		for (tuple <int, int, int> currEdge : edges) {
			int u, v, cost;
			tie(u, v, cost) = currEdge;

			if (minCost[u] + cost < minCost[v]) 
			       minCost[v] = minCost[u] + cost;
		}

	for (tuple <int, int, int> currEdge : edges) {
		int u, v, cost;
		tie(u, v, cost) = currEdge;

		if (minCost[u] + cost < minCost[v])
			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.push_back(make_tuple(u, v, cost));
	}
	
	if (!bellmanFord(1))
		cout << "Ciclu negativ!";
	else
		for (int i = 2; i <= n; i++) 
			cout << minCost[i] << ' ';

	return 0;
}