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


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("bellmanford.in","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;
 for(l=1;l<n;l++)
  {sf=cap;cap=0;
   for(i=1;i<=sf;i++)b[i]=c[i];
  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]){d[k]=d[b[j]]+a[0][i];pre[k]=b[j];c[++cap]=k;}
      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;
}