#include<stdio.h>
#include<queue>
#include<string.h>
#include<stdlib.h>
#define oo 0x3f3f3f3f
#define dim 50010
using namespace std;

int *A[dim],*C[dim],n,m,i,x,y,c,ciclu,viz[dim],cnt[dim],best[dim],in,sf;
queue<int> Q;

int main()
{
	FILE *f=fopen("bellmanford.in","r"), *g=fopen("bellmanford.out","w");
	
	fscanf(f,"%d %d",&n,&m );
	
	for(i=1;i<=n;i++)
	{	A[i]=(int*) realloc(A[i],sizeof(int));
		A[i][0]=0;	
		C[i]=(int*) realloc(C[i],sizeof(int));
		C[i][0]=0;
	}
	
	for(i=1;i<=m;i++)
	{
		fscanf(f,"%d %d %d",&x,&y,&c);
		
		A[x][0]++;
		A[x]=(int *)realloc(A[x],(A[x][0]+1) * sizeof(int));
		A[x][A[x][0]]=y;
	
		C[x][0]++;
		C[x]=(int *)realloc(C[x],(C[x][0]+1) * sizeof(int));
		C[x][C[x][0]]=c;	
	}
	
	memset(best,oo,sizeof(best));
	best[1]=0;
	
	Q.push(1); cnt[1]=1;
		
	while(!Q.empty() && !ciclu)
	{
		x=Q.front();
		Q.pop();
		viz[x]=0;
		for(i=1;i<=A[x][0];i++)
		{
			y=A[x][i];
			if(best[y] > best[x] + C[x][i] )
			{
				best[y] = best[x] + C[x][i];
				cnt[y]++;
				
				if(cnt[y]==n){ ciclu=1; break;}
				if(!viz[y]) {Q.push(y); viz[y]=1;}
			}
		}	
	}
	if(ciclu)
		fprintf(g,"Ciclu negativ!\n");
	else
		{	for(i=2;i<=n;i++)
				fprintf(g,"%d ",best[i]);
			fprintf(g,"\n");	}
		
fclose(f);
fclose(g);	
return 0;
}