#include<cstdio>
#define MAX 50005
#define INFINIT 2000000000
using namespace std;
struct nod{
    int info,c;
    nod *next;
};
struct coada{
    int capat;
    coada *nex;
};

nod *G[MAX];
int n,m,v[MAX],d[MAX],apariti[MAX];

void addarc(int a,int b,int c)
{
    nod *p=new nod;
    p->info=b;
    p->c=c;
    p->next=G[a];
    G[a]=p;
}

int bmf(int sursa)
{
    coada *st, *dr;
    int k;
    st=new coada;
    st->capat=sursa;
    st->nex=NULL;
    dr=st;
    v[sursa]=1;
    d[sursa]=0;
    while(st)
    {
        k=st->capat;
        v[k]=0;
        if(d[k]<INFINIT)
        for(nod *p=G[k]; p ; p=p->next)
            if( (d[k]+p->c) < d[p->info] )
            {
                int i=p->info;
                d[i]=d[k]+p->c;
                if(v[i]==0)
                {
                    if(apariti[i]>n)
                        return 1;
                    v[i]=1;
                    apariti[i]++;
                    coada *q=new coada;
                    q->capat=i;
                    q->nex=NULL;
                    dr->nex=q;
                    dr=dr->nex;
                }
            }
        coada *t=st;
        st=st->nex;
        delete t;
    }
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d %d", &n, &m);
    int i;
    for(i=1;i<=m;i++)
    {
        int x,y,c;
        scanf("%d %d %d", &x, &y, &c);
        addarc(x,y,c);
    }
    for(i=1;i<=n;i++)
        d[i]=INFINIT;
    if(bmf(1)==1)
        printf("Ciclu negativ!");
    else
        for(i=2;i<=n;i++)
            printf("%d ", d[i]);
    return 0;
}