#include <bits/stdc++.h>

using namespace std;

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

const int MAXN = 5e4;
const int MAXM = 25e4;

int n, m;
vector<pair<int, int> > g[MAXN + 1];
int dist[MAXN + 1], cnt[MAXN + 1];
queue<int> q;
bool used[MAXN + 1];

int main() {
	in >> n >> m;
	memset(dist, 0x3f, sizeof (dist));

	for (int i = 1; i <= m; ++ i) {
		int a, b, c;
		in >> a >> b >> c;
		g[a].push_back({b, c});
	}

	bool neg_cycle = false;
	int cur = 1;
	q.push(cur);
	used[cur] = true;
	dist[cur] = 0;
	cnt[cur] = 1;
	while (q.size() && !neg_cycle) {
		cur = q.front();
		q.pop();
		used[cur] = false;
		for (auto x : g[cur]) {
			if (dist[x.first] > dist[cur] + x.second) {
				dist[x.first] = dist[cur] + x.second;
				if (!used[x.first]) {
					used[x.first] = true;
					q.push(x.first);
					if (++cnt[x.first] >= n)
						neg_cycle = true;
				}
			}
		}
	}

	if (neg_cycle)
		out << "Ciclu negativ!";
	else
		for (int i = 2; i <= n; ++ i) out << dist[i] << ' ';

	return 0;
}