#include <bits/stdc++.h>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
struct muchie{
	int nod, cost;
};
vector<muchie> g[50005];
bool viz[50005], negativ;
int dis[50005], cnt[50005];
queue<int> q;
int n, m;
void bellmanford()
{
	while (!q.empty() && !negativ)
	{
		int nod = q.front();
		q.pop();
		viz[nod] = false;
		for (auto i : g[nod])
			if (dis[i.nod] > dis[nod] + i.cost)
			{
				dis[i.nod] = dis[nod] + i.cost;
				if (!viz[i.nod])
				{
					q.push(i.nod);
					viz[i.nod] = true;
					++cnt[i.nod];
					if (cnt[i.nod] > n)
						negativ = true;
				}
			}
	}
}
int main()
{
	fin >> n >> m;
	for (int i = 1; i <= m; ++i)
	{
		int x;
		muchie yc;
		fin >> x >> yc.nod >> yc.cost;
		g[x].push_back(yc);
	}
	for (int i = 1; i <= n; ++i)
		dis[i] = 1000000000;
	dis[1] = 0;
	viz[1] = true;
	cnt[1] = 1;
	q.push(1);
	bellmanford();
	if (negativ == true)
		fout << "Ciclu negativ!";
	else
		for (int i = 2; i <= n; ++i)
			fout << dis[i] << " ";
	return 0;
}