#include<fstream>
#define DIM 50005
#define INF 99999999
using namespace std;
int S,N,M,K,i,I,B[DIM],D2[DIM],ok,is,ic,C[DIM],D[DIM],V[DIM];


struct nod{
	int inf,dist;
	nod* adr;
}*A[DIM],*p,*q;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");


void citire(){
	int x,y,d;
	f>>N>>M;
	for(i=1;i<=M;i++)
	{
		f>>x>>y>>d;
		p=new nod;
		p->inf=y;
		p->dist=d;
		p->adr=A[x];
		A[x]=p;

	
	}


}
void belman_ford(){
	for(i=2;i<=N;i++)
		D[i]=INF;
	
	B[1]=1;
	C[1]=1;
	V[1]++;
	ic=is=1;
	ok=1;
	while ( ic<=is && ok )
	{
		p=A[C[ic]];
		B[C[ic]]=0;
		for(;p;p=p->adr)
		{
			if(D[p->inf]>D[C[ic]]+p->dist)
				{
					D[p->inf]=D[C[ic]]+p->dist;
					if(B[p->inf]==0)
					{
						if(V[p->inf]<=N-1)
							V[p->inf]++;
						else{
							 ok=0;
							return;
						}
						B[p->inf]=1;
						C[++is]=p->inf;
					}				
				}	
			
		}
		ic++;
	}
		
	for(i=1;i<=N;i++)
		if(D[i]==INF)
			D[i]=0;




}
void afis(){
	if(ok)
	for(i=2;i<=N;i++)
		g<<D[i]<<" ";
	else 
		g<<"Ciclu negativ!";

}
int main (){

	citire();
	belman_ford();
	afis();
	return 0;
}