#include<iostream>
#include<stdio.h>
#include<queue>

using namespace std;


struct Edge
{
	int x, y;

	int cost;

	int timesUsed;
};

int D[50010];



int main()
{
#ifndef LOCAL_JUDGE
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);
#endif

	int N, M;

	cin >> N >> M;

	queue<Edge> Q;



	for(int i=1;i<=M;++i)
	{
		int x, y, c;

		cin >> x >> y >> c;

		Q.push({ x,y,c,1 });
	}
	
	D[1] = 0;

	for (int i = 2; i <= N; ++i)
		D[i] = 1 << 30;

	while (Q.size())
	{
		auto edge = Q.front();

		if (D[edge.x] + edge.cost < D[edge.y])
		{
			D[edge.y] = D[edge.x] + edge.cost;

			edge.timesUsed++;

			Q.push(edge);
		}

		if (edge.timesUsed > N)
		{
			cout << "Ciclu Negativ!\n";

			return 0;
		}

		Q.pop();
	}

	for (int i = 2; i <= N; ++i)
		cout << D[i] << " ";


	return 0;
}