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

int v[3][250001];
int 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]=250000000;
	}
	v2[1]=0;
	s=0;
	for(j=1;j<n && s==0;j++){
		s=1;
		for(i=0;i<m;i++){
			if(v2[v[0][i]]+v[2][i]<v2[v[1][i]]){
				v2[v[1][i]]=v2[v[0][i]]+v[2][i];
				s=0;
			}
		}
	}
	
	s=0;		
	for(i=0;i<m;i++){
		if(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,"%d ",v2[i]);		
		}
	}

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