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

#define NMAX 51000
#define pb push_back
#define INF 1000000000

using namespace std;

struct nod{int next, cost;};

queue<int> Q;
vector<nod> A[NMAX];
int N, M, Count[NMAX], Cost[NMAX];

void Citire(void)
{
	ifstream fin("bellmanford.in");
	
	int i, x;
	nod a;
	
	fin >>N >>M;
	
	for (i = 1; i <= N; i++)
	{
		fin >>x >>a.next >>a.cost;
		A[x].pb(a);
	}
	
	fin.close();
}

int Rezolva(void)
{
	int nC, i;
	
	for (i = 1; i <= N; i++)
		Cost[i] = INF;
	
	Q.push(1);
	Count[1]++;
	Cost[1] = 0;
	
	while(!Q.empty())
	{
		nC = Q.front();
		Q.pop();
		
		for (i = 0; i < A[nC].size(); i++)
		{
			if (Cost[nC] + A[nC][i].cost < Cost[A[nC][i].next])
			{
				Cost[A[nC][i].next] = Cost[nC] + A[nC][i].cost;
				Q.push(A[nC][i].next);
				Count[A[nC][i].next]++;
				
				if (Count[A[nC][i].next] >= N)
					return 1;
			}
		}
		
	}
	return 0;
}

void Afiseaza(int neg)
{
	ofstream fout("bellmanford.out");
	
	if (neg)
		fout <<"Ciclu negativ!";
	else
		for (int i = 2; i <= N; i++)
			fout <<Cost[i] <<' ';
	
	fout.close();
}

int main()
{
	Citire();
	
	int negativ = Rezolva();
	
	Afiseaza(negativ);
	
	return 0;
}