#include<fstream>
#include<stdio.h>
using namespace std;
#define infile "bellmanford.in"
#define outfile "bellmanford.out"
#define muchii 250010
#define nod 50010
ifstream fin (infile);
long n,m;
long t[3][muchii];
long s[nod];
long d[nod];
long c[2][nod];
long f[2][nod];

void read()
{
	long i,j,x,y,c;
	//scanf("%ld %ld",&n,&m);
	fin>>n>>m;
	for(i=1;i<=n;i++)
		s[i]=0;
	for(i=1;i<=m;i++)
	{
		//scanf("%ld %ld %ld",&x,&y,&c);
		fin>>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;
		f[0][i]=i;
	}
	f[0][0]=n;
	f[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<=f[k%2][0];i++)
		{
			p=f[k%2][i];
			//parcurgem vecinii lui p
			for(j=s[p];j;j=t[2][j])
				if(d[p]+t[1][j]<d[t[0][j]])
				{
					d[t[0][j]]=d[p]+t[1][j];
					if(c[(k+1)%2][t[0][j]]==0)
					{
						c[(k+1)%2][t[0][j]]=1;
						l++;
						f[(k+1)%2][l]=t[0][j];
					}
				}
		}
		f[(k+1)%2][0]=l;
	}
	if(f[(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);
	fin.close();
	fclose(stdout);
	return 0;
}