#include<cstdio>
#include<vector>
using namespace std;

#define maxn 50001
#define INF 1000000000
#define maxm 250001

struct muchii
{int x,y,c;};

int n,m ;
muchii mc[maxm] ;
int d[maxn] ;

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);
		mc[i].x = a ;
		mc[i].y = b ;
		mc[i].c = c ;
	}

	for(int i=2;i<=n;++i)
		d[i] = INF ;
	int last = 1;
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			int x = d[mc[j].y];
			d[mc[j].y] = min ( d[mc[j].y] , d[mc[j].x] + mc[j].c ) ;
			if( x != d[mc[j].y])
				last = i;
		}	
	}	
	if( last == n ) {
		printf("Ciclu negativ!\n");
		return 0;
	}
	for(int i=2;i<=n;++i)
		printf("%d ",d[i]);
	
	return 0;
	
}