#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

#define inf 2000000
using namespace std;

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

int n, m, dp[50005], cnt[50005], isCycle;
vector <pair<int, int> > a[50005];
queue <int> Q;
int main()
{
	int i, x, y, cost;
	fin >> n >> m;
	for (i = 1; i <= m; i++)
	{
		fin >> x >> y >> cost;
		a[x].push_back({ y, cost });
	}

	for (i = 1; i <= n; i++)
		dp[i] = inf;
	dp[1] = 0;
	Q.push(1);
	cnt[1] = 1;
	isCycle = 0;

	while (!Q.empty() and isCycle == 0)
	{
		x = Q.front();
		Q.pop();
		for (auto w : a[x])
		{
			if (dp[w.first] > w.second + dp[x])
			{
				cnt[w.first]++;
				if (cnt[w.first] > n)
				{
					isCycle = 1;
					break;
				}
				dp[w.first] = w.second + dp[x];
				Q.push(w.first);
			}
		}
	}

	if (isCycle == 1)
		fout << "Ciclu negativ!\n";
	else
		for (i = 2; i <= n; i++)
			fout << dp[i] << " ";

	return 0;
}