#include<stdio.h>
#define INF 20000001
#define Nmx 50002

int n,m,viz[Nmx],cost[Nmx];
struct much
{
    int x,y,c;
};
much X[250001];
int nr;

struct nod
{
    int inf;
    int cost;
    nod *urm;
};
nod *G[Nmx];

void add(int x,int y,int c)
{
    nod *aux=new nod;
    aux->inf=y;
    aux->cost=c;
    aux->urm=G[x];
    G[x]=aux;
}

void citire()
{
    int x,y,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        X[++nr].x=x;X[nr].y=y;X[nr].c=c;
        add(x,y,c);
    }
}

int esteciclunegativ()
{
    for(int i=1;i<=m;++i)
        if(cost[X[i].x]+X[i].c<cost[X[i].y])
            return 1;
    return 0;
}

void solve()
{
    int S[200001],st,dr;
    st=dr=1;
    for(int i=2;i<=n;++i)
        cost[i]=INF;
    S[1]=1;viz[1]=1;
    int pas=0;
    while(st<=dr&&pas<=n*m*1LL)
    {
        pas++;
        viz[S[st]]=0;
        for(nod *p=G[S[st]];p;p=p->urm)
            if(cost[S[st]]+p->cost<cost[p->inf])
            {
                cost[p->inf]=cost[S[st]]+p->cost;
                if(!viz[p->inf])
                {
                    viz[p->inf]=1;
                    S[++dr]=p->inf;
                }
            }
        ++st;
    }
    if(esteciclunegativ())
        printf("Ciclu negativ!\n");
    else
    for(int i=2;i<=n;++i)
    {
        printf("%d ",cost[i]);
    }
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    citire();
    solve();
    return 0;
}