//============================================================================
// Name        : Bellman-Ford.cpp
// Author      : Razvan
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <bits/stdc++.h>

#define Nmax 50001
#define oo 0x3f3f3f3f

using namespace std;

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

vector < pair <int, int> > G[Nmax];
queue <int> Coada;

int N, M;
bool InCoada[Nmax];
int D[Nmax];
int Viz[Nmax];

void Read()
{
	int x, y, c;
	fin >> N >> M;
	for (int i=1; i<=M; i++)
	{
		fin >> x >> y >> c;
		G[x].push_back(make_pair(y,c));
	}
}

int BellmanFord(int NodStart)
{
	D[NodStart] = 0;
	InCoada[NodStart] = true;
	Viz[NodStart] = 1;
	Coada.push(NodStart);
	while (!Coada.empty())
	{
		int Nod = Coada.front();
		Viz[Nod]++;
		if (Viz[Nod] >= N)
			return false;
		InCoada[Nod] = false;
		Coada.pop();
		for (unsigned int i=0; i<G[Nod].size(); i++)
		{
			int Vecin = G[Nod][i].first;
			int Cost = G[Nod][i].second;
			if (D[Vecin] > D[Nod] + Cost)
			{
				D[Vecin] = D[Nod] + Cost;
				if (InCoada[Vecin] ==  false)
				{
					Coada.push(Vecin);
					InCoada[Vecin] = true;
				}
			}
		}
	}
	return true;
}

int main() {
	Read();
	//int NodStart;
	//fin >> NodStart;
	for (int i=1; i<=N; i++)
	{
		D[i] = oo;
	}
	if (BellmanFord(1) == false)
		fout << "Ciclu negativ!";
	else
	{
		for (int i=2; i<=N; i++)
		{
			fout << D[i] << " ";
		}
	}
	return 0;
}