#include<stdio.h>
#define Nmx 50005
#define INF 0x3f3f3f3f

int n,m,dist[Nmx],viz[Nmx];
struct nod
{
    int inf,c;
    nod *urm;
};
nod *G[Nmx];

void add(int x,int y,int c)
{
    nod *aux=new nod;
    aux->inf=y;
    aux->c=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);
        add(x,y,c);
    }
    for(int i=1;i<=n;++i)
        dist[i]=INF;
}

void solve()
{
    int Q[Nmx*10],st,dr;
    st=dr=1;
    Q[1]=1;dist[1]=0;
    viz[1]=1;int ng=0;
    while(st<=dr&&!ng)
    {
        viz[Q[st]]--;
        for(nod *p=G[st];p&&!ng;p=p->urm)
            if(dist[p->inf]>dist[Q[st]]+p->c)
            {
                dist[p->inf]=dist[Q[st]]+p->c;
                if(viz[p->inf]==0)
                {
                    if(viz[p->inf]>n)
                        ng=1;
                else
                    {
                        Q[++dr]=p->inf;
                        viz[p->inf]++;
                    }
                }
            }
        ++st;
    }
    if(ng==1)
        printf("Ciclu negativ!\n");
    else
    for(int i=2;i<=n;++i)
        printf("%d ",dist[i]);
}


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