#include <iostream>
#include<stdio.h>

using namespace std;

struct graf
    {
        int nod;
        int cost;
        graf *adr;
    };

int viz[50001],c[50001],n,m,k,s[250001];
graf *l[250001],*a,*p;



void add(int x, int y,int z)
{
    a=new graf;
    a->nod=y;
    a->cost=z;
    a->adr=l[x];
    l[x]=a;
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d %d",&n,&m);
    int x,y,z;
    for(int i=1;i<=m;i++)
        {
            scanf("%d %d %d",&x,&y,&z);
            add(x,y,z);
        }

    for(int i=0;i<=n;i++)
        c[i]=10000;

    k=1;
    s[k]=1;
    viz[k]=1;
    c[k]=0;

    for(int i=1;i<=k;i++)
        {
            p=l[s[i]];
            while(p)
                {
                    if(p->cost+c[s[i]]<c[p->nod])
                        {
                            c[p->nod]=p->cost+c[s[i]];
                            s[++k]=p->nod;
                            viz[p->nod]++;
                            if(viz[p->nod]>=n)
                                {
                                    printf("Ciclu negativ!");
                                    return 0;
                                }
                        }
                    p=p->adr;
                }
        }
    for(int i=2;i<=n;i++)
        printf("%d ",c[i]);
    return 0;
}