#include<stdio.h>
#define DIM 50005
struct nod
{
    int x,c;
    nod *urm;
} *lst[DIM];
int n,a[DIM];
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,m,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);
        add (x,y,c);
    }
}
void solve ()
{
    nod *p;
    int st,dr,c[DIM];
    c[st=dr=1]=1;
    while(st<=dr)
    {
        for(p=lst[c[st]];p;p=p->urm)
            if(a[c[st]]+p->c<a[p->x])
            {
                a[p->x]=a[c[st]]+p->c;
                c[++dr]=p->x;
            }
        ++st;
    }
}
void show ()
{
    int i;
    for(i=2;i<=n;++i)
        if(a[i]==1<<18)
        {
            printf("Ciclu negativ!");
            return ;
        }
    for(i=2;i<=n;++i)
        printf("%d ",a[i]);
}
int main ()
{
    freopen ("bellmanford.in","r",stdin);
    freopen ("bellmanford.out","w",stdout);
    read ();
    solve ();
    show ();
    return 0;
}