#include<stdio.h>
const int N=50001;
struct P
{
int x,y;
P *u;
};
P *g[N],*p;
int m,n,i,k,l,r,d[N],e[7*N],v[N],u[N];
int main()
{
freopen("bellmanford.in","r",stdin),freopen("bellmanford.out","w",stdout),scanf("%d%d",&n,&m);
while(m--)
{
scanf("%d%d%d",&k,&l,&r);
p=new P;
p->x=l,p->y=r,p->u=g[k],g[k]=p;
}
for(i=2;i<=n;i++)
d[i]=N;
for(k=l=r=0,e[r++]=v[1]=1;l<r&&!k;)
for(i=e[l++],v[i]=0,p=g[i];p&&!k;p=p->u)
if(d[p->x]>d[i]+p->y)
{
d[p->x]=d[i]+p->y;
if(!v[p->x])
if(u[p->x]>n)
k=1;
else
e[r++]=p->x,v[p->x]=1,u[p->x]++;
}
if(k)
printf("Ciclu negativ!");
else
for(i=2;i<=n;i++)
printf("%d ",d[i]);
}