#include<stdio.h>
#include<vector>
#define INF 1<<29
using namespace std;
int n,m, sw=1, d[50005];

struct nod
{
	int a,b,c;
} t;

vector < nod > V;

int main()
{
	freopen("bellmanford.in","r", stdin);
	freopen("bellmanford.out","w", stdout);
	
	scanf("%d %d", &n,  &m);
	for(int i=1; i<=m;i++)
	{
		int a,b,c;
		scanf("%d %d %d", &a, &b, &c);
		t.a=a;
		t.b=b;
		t.c=c;
		V.push_back( t ); 
	}
	
	for(int i=2; i<=n; i++)
		d[i] = INF;
	
	for(int i=1; i<n; i++)
	{
		sw=0;
		for(int j=0; j< V.size(); j++)
			if(  d [ V[j].b ] > d [ V[j].a ] + V[j].c )
				d [ V[j].b ] = d [ V[j].a ] + V[j].c, sw=1;				
		if( !sw ) break;
	}
	
	sw=1;
	
	for(int j=0; j< V.size(); j++)
		if(  d [ V[j].b ] > d [ V[j].a ] + V[j].c )
			sw=0;				
	
	if(sw)
		for(int i=2; i<=n;i++)
			printf("%d ", d[i]);
		else printf("Ciclu negativ!");
	
	return 0;
}