#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]=9223372036854775806;
	}
	v2[1]=0;
	for(j=0;j<n-1;j++){
		for(i=0;i<m;i++){
			if((long long)v[0][i]+v[2][i]<v2[v[1][i]]){
				v2[v[1][i]]=(long long)v[0][i]+v[2][i];
			}
		}
	}
	
	s=0;
	for(i=0;i<m;i++){
		if(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;
}