#include <stdio.h>
#include <stdlib.h>

int v[3][250001];
long long v2[50001];

int main(){
	int n,m,i,j,s;
	FILE *fin,*fout;
	fin=fopen("bellmanford.in","r");
	fout=fopen("bellmanford.out","w");
	fscanf(fin,"%d%d",&n,&m);

	for(i=0;i<m;i++){
		fscanf(fin,"%d%d%d",&v[0][i],&v[1][i],&v[2][i]);
	}
	for(i=0;i<=n;i++){
		v2[i]=2500000000;
	}
	v2[1]=0;
	j=0;
	s=0;
	while(j<n-1 && s==0){
		s=1;
		for(i=0;i<m;i++){
			if((long long)v2[v[0][i]]+v[2][i]<v2[v[1][i]]){
				v2[v[1][i]]=(long long)v2[v[0][i]]+v[2][i];
				s=0;
			}
		}
		j++;
	}
	
	if(j==n-1){
		s=0;
		for(i=0;i<m;i++){
			if((long long)v2[v[0][i]]+v[2][i]<v2[v[1][i]]){
				s=1;
			}	
		}
	}
	if(s==1){
		fprintf(fout,"Ciclu negativ!");
	}else{
		for(i=2;i<=n;i++){
			fprintf(fout,"%lld ",v2[i]);		
		}
	}

	
	fclose(fin);
	fclose(fout);
	return 0;
}