#include <bits/stdc++.h>

using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

int n, m, x, y, c, d[50100], cnt[50100];
queue<int> q;
vector<pair<int, int> > v[50100];

int main() {
	in >> n >> m;
	for (int i = 1; i <= m; i++) {
		in >> x >> y >> c;
		v[x].push_back({c, y});
	}
	
	for (int i = 1; i <= n; i++)
		d[i] = 2e9;
	d[1] = 0;
	q.push(1);
	
	while (!q.empty()) {
		x = q.front();
		q.pop();
		
		for (auto y : v[x])
			if (d[x] + y.first < d[y.second]) {
				if (cnt[y.second] == n)
					return out << "Ciclu negativ!", 0;
				cnt[y.second]++;
				d[y.second] = d[x] + y.first;
				q.push(y.second);
			}
	}
	
	for (int i = 2; i <= n; i++)
		out << d[i] << ' ';

	return 0;
}