#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);
ofstream fout (outfile);
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,q,r;
	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])
			{q=t[1][j];r=t[0][j];
				if(d[p]+q<d[r])
				{
					d[r]=d[p]+q;
					if(c[(k+1)%2][r]==0)
					{
						c[(k+1)%2][r]=1;
						l++;
						f[(k+1)%2][l]=r;
					}
				}
			}
		}
		f[(k+1)%2][0]=l;
	}
	if(f[(n-1)%2][0]!=0)
	{
		//printf("Ciclu negativ!");
		fout<<"Ciclu negativ!";
	}
	else
		for(i=2;i<=n;i++)
		{
//			printf("%ld ",d[i]);
			fout<<d[i]<<" ";
		}
	
}
int main()
{
	//freopen(infile,"r",stdin);
	//freopen(outfile,"w",stdout);
	read();
	init();
	bellmanFord();
	//fclose(stdin);
	fin.close();
	fout.close();
	//fclose(stdout);
	return 0;
}