#include <stdio.h>
long circuit,a[3][260],d[50],i,j,st[50],fin[50],k,l,pre[50],n,m,x,y,z,sf,cap,b[50],c[50],v[50];


/*int circuit()
{for(j=1;j<=n;j++)
  {i=st[j];
   while(i)
    {k=a[1][i];
     if(d[k]>d[j]+a[0][i])return 0;
     i=a[2][i];
    }
  }
 return 1;
}*/

int main()
{freopen("bellfor1.txt","r",stdin);freopen("bellmanford.out","w",stdout);
 fscanf(stdin,"%ld%ld",&n,&m);
 for(i=1;i<=m;i++)
  {fscanf(stdin,"%ld%ld%ld",&x,&y,&z);
   if(fin[x]==0){st[x]=fin[x]=l+1;l++;a[1][l]=y;a[0][l]=z;}
	  else{a[2][fin[x]]=l+1;fin[x]=l+1;l++;a[1][l]=y;a[0][l]=z;}
  }
 for(i=2;i<=n;i++)d[i]=2000000001;
 cap=1;c[1]=1;
 for(l=1;l<=n;l++)
  {sf=cap;cap=0;
   for(i=1;i<=sf;i++){b[i]=c[i];v[b[i]]=0;}
  for(j=1;j<=sf;j++)
   {i=st[b[j]];
    while(i)
     {k=a[1][i];
      if(d[k]>d[b[j]]+a[0][i]||pre[k]==0)
       {d[k]=d[b[j]]+a[0][i];pre[k]++;if(pre[k]==n-1)circuit=1;
	if(v[k]==0){cap++;c[cap]=k;v[k]=1;}
       }
      i=a[2][i];
     }
   }
  }
 if(!circuit)
  {for(i=2;i<=n;i++)printf("%ld ",d[i]);
  }
  else printf("Ciclu negativ!");
 fclose(stdin);fclose(stdout);
 return 0;
}