#include<stdio.h>
struct nod
    {
        int inf;
        int cost;
        nod *ad;
    };

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



void add(int x, int y,int z)
{
    a=new nod;
    a->inf=y;
    a->cost=z;
    a->ad=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]=10;

    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->inf])
                        {
                            c[p->inf]=p->cost+c[s[i]];
                            s[++k]=p->inf;
                            viz[p->inf]++;
                            if(viz[p->inf]>=n)
                                {
                                    printf("Ciclu negativ!");
                                    return 0;
                                }
                        }
                    p=p->ad;
                }
        }
    for(int i=2;i<=n;i++)
        printf("%d ",c[i]);
    return 0;
}