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

int main() {
	fin >> n >> m;
	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;

	c.push(make_pair(make_pair(0, 1), 0));
	while (!c.empty()) {
		int money = -c.top().first.first;
		int act = c.top().first.second;
		int dist = c.top().second;
		c.pop();

		if (dist == n) {
			fout << "Ciclu negativ!";
			return 0;
		}


		for (pair<int, int> edge : edges[act])
			if (money + edge.second < sol[edge.first]) {
				sol[edge.first] = money + edge.second;
				c.push(make_pair(make_pair(-sol[edge.first], edge.first), dist + 1));
			}
	}

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