#include<iostream>
#include<fstream>
#include<queue>
#include<vector>
std::ifstream in("bellmanford.in");
std::ofstream out("bellmanford.out");
#define MAX_W 100001
using namespace std;
vector<pair<int, int>>g[100001];
int n, m;
vector<int>d, inqueue, numberofint;
void bellman_ford() {
	int cycle = 0;
	d = inqueue = numberofint = vector<int>(n + 1);
	for (int i = 1; i <= n; i++) d[i] = 0x3F3F3F3F;
	queue<int>coada;
	coada.push(1);
	inqueue[1] = 1, d[1] = 0, numberofint[1] = 1;
	while (!coada.empty() && numberofint[coada.front()] <= n) {
		int node = coada.front();
		coada.pop();
		inqueue[node] = 0;
		for (auto i : g[node]) {
			if (d[node] + i.second < d[i.first]) {
				d[i.first] = d[node] + i.second;
				coada.push(i.first);
				if (!inqueue[i.first]) {
					numberofint[i.first]++;
					coada.push(i.first);
					inqueue[i.first] = 1;
				}
			}
		}
		cycle = !coada.empty();
	}
	if (!cycle) for (int i = 2; i <= n; i++) out << d[i] << " ";
	else out << "Ciclu negativ!";
}
int main() {
	in >> n >> m;
	while (m--) {
		int u, v, cost;
		in >> u >> v >> cost;
		g[u].push_back({ v,cost });
	}
	bellman_ford();
	return 0;
}