#include <bits/stdc++.h>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n, m, sol[50100], cnt_in_queue[50100];
vector<pair<int, int> > edges[50100];
bitset<50100> in_queue;
struct pos {
	int nod, cost, dist;
};
priority_queue<pair<int, int> > c;

int main() {
	fin >> n >> m;
	if (n == 1)
		return 0;
	for (int i = 1; i <= m; i++) {
		int a, b, cost;
		fin >> a >> b >> cost;
		edges[a].push_back(make_pair(b, cost));
	}

	for (int i = 1; i <= n; i++)
		sol[i] = INT_MAX;
	sol[1] = 0;

	c.push(make_pair(0, 1));
	while (!c.empty()) {
		int cost_act = c.top().first;
		int act = c.top().second;
		c.pop();
		in_queue[act] = false;
		cnt_in_queue[act]++;

		if (cnt_in_queue[act] == n) {
			fout << "Ciclu negativ!";
			return 0;
		}

		for (pair<int, int> edge : edges[act])
			if (cost_act + edge.second < sol[edge.first]) {
				sol[edge.first] = cost_act + edge.second;
				if (!in_queue[edge.first])
					c.push(make_pair(sol[edge.first], edge.first));
			}
	}

	for (int i = 2; i <= n; i++)
		fout << sol[i] << ' ';
    return 0;
}