#include<stdio.h>

#define inf 0x3f3f3f
#define Nmax 50010
#define Mmax 250010
#define mod 250010

struct nod
{
    int info,cost;
    nod *urm;
} *l[Nmax];

int n,m;
int D[Nmax],v[Nmax];
int c[Mmax];

void cit();
void add(nod *&inc,int info1,int info2)
{
    nod *p=new nod;
    p->info=info1;
    p->cost=info2;
    p->urm=inc;
    inc=p;
}

int bellman()
{
    for(int i=2;i<=n;++i)
        D[i]=inf;
    int st=1,dr=1;
    c[1]=1;
    v[1]=1;
    
    for( ; st<=dr ; ++st)
        for(nod *t=l[ c[st%mod] ] ; t ; t=t->urm)
            {
            if (D[ t->info ] > D[ c[st%mod] ] + t->cost)
                {
                D[t->info] = D[ c[st%mod] ] + t->cost;
                if (v[t->info] < st)
                    {
                    v[t->info]=++dr;
                    c[dr%mod]=t->info;
                    }
                }
            if (dr>n*m)
                return 0;
            }
            
    return 1;
}

void solve()
{
    if (!bellman())
        {
        printf("Ciclu Negativ!\n");
        return ;
        }
    
    for(int i=2;i<=n;++i)
        printf("%d ",D[i]);
    printf("\n");
}

int main()
{
    cit();
    solve();
    return 0;
}

void cit()
{
    int a,b,d;
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
        {
        scanf("%d%d%d",&a,&b,&d);
        add(l[a],b,d);
        }
}