#include<stdio.h>
#define infile "bellmanford.in"
#define outfile "bellmanford.out"
#define muchii 250010
#define nod 50010

long n,m;
long t[3][muchii];
long s[nod];
long d[nod];
long c[2][nod];

void read()
{
	long i,j,x,y,c;
	scanf("%ld %ld",&n,&m);
	for(i=1;i<=n;i++)
		s[i]=0;
	for(i=1;i<=m;i++)
	{
		scanf("%ld %ld %ld",&x,&y,&c);
		t[0][i]=y;
		t[1][i]=c;
		t[2][i]=s[x];
		s[x]=i;
	}
}

void init()
{
	long i;
	for(i=1;i<=n;i++)
		d[i]=200000000;
	d[1]=0;
	for(i=s[1];i;i=t[2][i])
		d[t[0][i]]=t[1][i];
}

void bellmanFord()
{
	long l,i,j,k,p;
	for(i=1;i<=n;i++)
		c[0][i]=1;
	c[0][0]=n;
	c[1][0]=0;
	for(k=0;k<=n-2;k++)
	{
		//etapa k;
		for(i=1;i<=n;i++)
			c[(k+1)%2][i]=0;
		l=0;
		for(i=1;i<=n;i++)
		if(c[k%2][i]==1)
		{
			//parcurgem vecinii lui i;
			for(j=s[i];j;j=t[2][j])
				if(d[i]+t[1][j]<d[t[0][j]])
				{
					d[t[0][j]]=d[i]+t[1][j];
					l++;
					c[(k+1)%2][t[0][j]]=1;
				}
		}
		c[(k+1)%2][0]=l;
	}
	if(c[(n-1)%2][0]!=0)
		printf("Ciclu negativ!");
	else
		for(i=2;i<=n;i++)
			printf("%ld ",d[i]);
	
}
int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);
	read();
	init();
	bellmanFord();
	fclose(stdin);
	fclose(stdout);
	return 0;
}