#include<stdio.h>
#define N 50001
long n,m,i,j,k,c,s1[N],s2[N],s3[N],p[N],d[N];
int main()
{freopen("bellmanford.in","r",stdin);
freopen("bellmanford.out","w",stdout);
scanf("%ld%ld",&n,&m);
for(k=1;k<=m;k++)
      {scanf("%ld%ld%ld",&i,&j,&c);
      s1[k]=i;
      s2[k]=j;
      s3[k]=c;}
for(i=1;i<=n;i++)
      {d[i]=1000;
      p[i]=0;}
d[1]=0;
for(i=1;i<=n;i++)
      {for(k=1;k<=m;k++)
      if(d[s2[k]]>d[s1[k]]+s3[k])
             {d[s2[k]]=d[s1[k]]+s3[k];
             p[s2[k]]=s1[k];}}
for(k=1;k<=m;k++)
if(d[s2[k]]>d[s1[k]]+s3[k])
      {printf("Ciclu negativ\n");
      return 1;}
for(i=2;i<=n;i++)
      printf("%ld ",d[i]);
fclose(stdin);
fclose(stdout);
return 0;}