#include<fstream>
#include<vector>
#include<iostream>
#include<chrono>
#include<queue>
using namespace std;

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

int D[50010];
int is_in_queue[50010];
int E[50010];
vector<pair<int,int> > G[50010];

queue<int> Q;

int main()
{
	int  N, M;

	in >> N >> M;

	for (int i = 1; i <= M; ++i)
	{
		int x, y, w;
		in >> x >> y >> w;

		G[x].push_back(make_pair(y, w));

	}

	Q.push(1);
	E[1]++;
	is_in_queue[1] = 1;

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

	D[1] = 0;

	while (Q.size())
	{
		int x = Q.front();
		if (E[x] <= N)
		{
			for (int i = 0; i < G[x].size(); ++i)
			{
					if (D[x] + G[x][i].second < D[G[x][i].first])
					{
						D[G[x][i].first] = D[x] + G[x][i].second;
						E[G[x][i].first]++;

						if (!is_in_queue[G[x][i].first])
						{
							is_in_queue[G[x][i].first] = 1;

							Q.push(G[x][i].first);
						}

					}
			}
		}
		else
		{
			out << "Ciclu negativ!";
			return 0;
		}
		is_in_queue[1] = 0;
		Q.pop();
	}

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


	return 0;
}