#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define NMAX 5005
#define MMAX 2505
#define INF 2e7
int n , m,x,y,z;
int t[NMAX],d[NMAX];
struct muchie
{
	int a,b,c;
}  e[MMAX];
void bellford()
{
	
	d[1]=0;
	for(int i=2;i<=n;++i)
	{
		
		d[i]=INF;
	}

	for(int i=1;i<n;++i)
		for(int j=1;j<=m;++j)
		{
			x=e[j].a;
			y=e[j].b;
			z=e[j].c;

			if( d[y]>d[x]+z )			
				d[y]=d[x]+z;
		}


}
int check()
{
	for(int j=1;j<=m;++j)
	{
		x=e[j].a;
		y=e[j].b;
		z=e[j].c;
		if(d[y]>d[x]+z) return 1;
	}
	return 0;
}

void citeste()
{
	scanf("%d %d",&n,&m);
	for ( int i=1 ;i<=m; ++i)	
		scanf("%d %d %d", &e[i].a,&e[i].b,&e[i].c);
}

int main()
{
	freopen("bellmanford.in", "r",stdin);
	freopen("bellmanford.out","w",stdout);
	citeste();
	bellford();
	if(check() )printf( "Ciclu negativ!\n" );
	else	
	 for(int i=2;i<=n;++i)printf("%d ",d[i]);
	
	return 0 ;
}