#include<stdio.h>
FILE *f,*g;
long i,n,m,x,y,z,c[50100],nr,t[4][1000100],inf,dist[50100],pr,u,st[1000100],p,fin[50100],ciclu[50100],ok;
int main()
{ f=fopen("bellmanford.in","r"); g=fopen("bellmanford.out","w");
  fscanf(f,"%ld%ld",&n,&m);
  for(i=1;i<=m;i++) 
    {  fscanf(f,"%ld%ld%ld",&x,&y,&z);
       if(c[x]==0) { nr++; c[x]=nr; t[1][nr]=y; t[3][nr]=z; fin[x]=nr; }
	   else { nr++; t[2][fin[x]]=nr; fin[x]=nr; t[1][nr]=y; t[3][nr]=z; }
	}
  inf=1000000000;
  for(i=2;i<=n;i++) dist[i]=inf; 
  pr=u=1; st[1]=1; ciclu[1]=1; ok=1;
  while(pr<=u&&ok)
   { p=c[st[pr]];
     while(p) 
	   { if(dist[st[pr]]+t[3][p]<dist[t[1][p]]) 
	        { u++; st[u]=t[1][p]; ciclu[t[1][p]]++; if(ciclu[t[1][p]]==n+1) ok=0; dist[t[1][p]]=dist[st[pr]]+t[3][p]; }
		 p=t[2][p];
	   }
	 pr++;
   }
  if(ok) for(i=2;i<=n;i++) fprintf(g,"%ld ",dist[i]); else fprintf(g,"Ciclu negativ!");
  fclose(g);
  return 0;
}