#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int NMax = 50005;
const int oo = (1 << 30);



ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int N, M;
int D[NMax];
bool InCoada[NMax];
vector <pair <int, int> > G[NMax];
int aparitii[NMax];
bool ciclu_negativ = false;
queue < int > Coada;

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

void bellmanford(int nodStart)
{
	for (int i = 1; i <= N; i++)
		D[i] = oo;
	D[nodStart] = 0;
	Coada.push(nodStart);
	InCoada[nodStart] = true;
	while (!Coada.empty()&& !ciclu_negativ)
	{
		int nodCurent = Coada.front();
		Coada.pop();
		InCoada[nodCurent] = false;
		for (int i = 0; i < G[nodCurent].size(); i++)
		{
			int Vecin = G[nodCurent][i].first;
			int Cost = G[nodCurent][i].second;
			if (D[nodCurent] + Cost < D[Vecin])
			{
				D[Vecin] = D[nodCurent] + Cost;
				if (InCoada[Vecin] == false)
				{
					Coada.push(Vecin);
					InCoada[Vecin] = true;
				}
				aparitii[Vecin]++;
				if (aparitii[Vecin] == N)
					ciclu_negativ = true;
			}
		}
	}
}

int main()
{
	Citeste();
	bellmanford(1);
	if (ciclu_negativ)
		fout << "Ciclu negativ!";
	else
		for (int i = 2; i <= N; i++)
			fout << D[i] << ' ';

	return 0;
}