#include<stdio.h>
#define DIM 50005
#define DIM2 250010
struct nod
{
    int x,c;
    nod *urm;
} *lst[DIM];
struct ok
{
    int x,y,c;
} muc[DIM2];
int n,a[DIM],v[DIM],m;
void add (int x,int y,int c)
{
    nod *p=new nod;
    p->x=y;
    p->c=c;
    p->urm=lst[x];
    lst[x]=p;
}
void read ()
{
    int i,x,y,c;
    scanf("%d%d",&n,&m);
    for(i=2;i<=n;++i)
        a[i]=1<<18;
    for(i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        muc[i].x=x;
        muc[i].y=y;
        muc[i].c=c;
        add (x,y,c);
    }
}
int solve ()
{
    nod *p;
    int st,dr,c[DIM2+100],aux;
    long long pas=1;
    c[st=dr=1]=v[1]=1;
    while(st<=dr)
    {
        aux=c[st%DIM2];
        for(p=lst[aux];p;p=p->urm)
            if(a[aux]+p->c<a[p->x])
            {
                a[p->x]=a[aux]+p->c;
                v[p->x]=1;
                ++dr;
                c[dr%DIM2]=p->x;
            }
        ++st;
        if(++pas>(long long)n*m)
            return 1;
    }
    for(int i=1;i<=m;++i)
        if(a[muc[i].x]+muc[i].c<a[muc[i].y])
            return 1;
    return 0;
}
void show ()
{
    int i,k=0;
    for(i=2;i<=n;++i)
        printf("%d ",a[i]);
}
int main ()
{
    freopen ("bellmanford.in","r",stdin);
    freopen ("bellmanford.out","w",stdout);
    read ();
    if(solve ())
        printf("Ciclu negativ!\n");
    else
        show ();
    return 0;
}