#include<stdio.h>
const int N=50001;
struct R
{
    int x,y;
    R *u;
}P;
P *g[N],*p
void A(P *p,int b,int c)
{
    P *q=new P;
    q->x=b,q->y=c,q->u=NULL,p=q;
}
int m,n,i,j,k,l,r,p,d[N]={N},e[1500000],a,b,c,v[50001],u[50001];
int main() {
    freopen("bellmanford.in","r",stdin),freopen("bellmanford.out","w",stdout),scanf("%d%d",&n,&m);
    while(m--)
        scanf("%d%d%d",&a,&b,&c),A(g[a],b,c);
    for(d[1]=0,e[r++]=v[1]=1;l<r&&!k;)
        for(j=e[l++],v[j]=0,p=g[j];p&&!k;p=p->u)
            if(d[p->x]>d[j]+p->y)
            {
                d[p->x]=d[j]+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]);
}