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

using namespace std;


struct Edge
{
	int x, y;

	int cost;

	int id;
};

int D[50010], E[300010];
 
vector<Edge> G[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, i});

		G[x].push_back({ x,y,c, i });
	}
	
	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;

			E[edge.y]++;

			for(int j=0;j<G[edge.y].size();++j)
			{
				Q.push(G[edge.y][j]);
			}
		}

		if (E[edge.y] > N)
		{
			cout << "Ciclu negativ!";

			return 0;
		}

		Q.pop();
	}

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


	return 0;
}