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

using namespace std;


struct Edge
{
	int x, y;

	int cost;
};

int D[50010], E[300010];
 
vector<Edge> G[50010]; 

int isInQueue[300010];



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;

		G[x].push_back({ x,y,c });


	
	}
	

	Q.push({ 1,0,0 });

	isInQueue[1] = 1;

	D[1] = 0;

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

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

		for (int j = 0; j < G[node.x].size(); ++j)
		{

			if (D[node.x] + G[node.x][j].cost < D[G[node.x][j].y])
			{
				D[G[node.x][j].y] = D[node.x] + G[node.x][j].cost;

				E[G[node.x][j].y]++;


				if (isInQueue[G[node.x][j].y] == 0)
				{
					Q.push({ G[node.x][j].y,0,0 });

					isInQueue[G[node.x][j].y] = 1;
				}

			}

	
		}

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

			return 0;
		}

		isInQueue[node.x] = 0;

		Q.pop();
	}

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


	return 0;
}