#include<stdio.h>
struct nod
{
    int vecin,cost;
    nod *adr;
};
nod *v[50001],*p;
void adaug(nod *&L,int v,int c)
{
    nod *p;
    p=new nod;
    p->vecin=v;
    p->cost=c;
    p->adr=L;
    L=p;
}
int N,M,i,x,y,c,k,vmin,d[50001],t[50001],viz[50001],pr,ul,coada[50001],nr,ok;
int main()
{
    freopen("dijkstra.in","rt",stdin);
    freopen("dijkstra.out","wt",stdout);
    scanf("%d %d",&N,&M);
    for(i=1;i<=N;i++)
    {
        v[i]=0;
    }
    for(i=1;i<=M;i++)
    {
        scanf("%d %d %d",&x,&y,&c);
        adaug(v[x],y,c);
    }
    for(i=1;i<=N;i++)
    {
        d[i]=1000000000;
        t[i]=0;
        viz[i]=0;
    }
    d[1]=0;
    coada[1]=1;
    pr=1;ul=1;nr=1;viz[1]=1;
    ok=0;
    k=0;
    while(!ok && k<N && nr!=0)
    {
        k++;
        ok=1;
        for(p=v[coada[pr]];p!=0;p=p->adr)
        {
            if(d[coada[pr]]+p->cost<d[p->vecin])
            {
                d[p->vecin]=d[coada[pr]]+p->cost;
                t[p->vecin]=coada[pr];
                ok=0;
                if(viz[p->vecin]==0)
                {
                    viz[p->vecin]=1;
                    ul++;
                    if(ul>N)
                    {
                        ul=1;
                    }
                    coada[ul]=p->vecin;
                    nr++;
                }
            }
        }
        viz[coada[pr]]=0;
        nr--;
        pr++;
        if(pr>N)
        {
            pr=1;
        }
    }
    for(i=2;i<=N;i++)
    {
        if(d[i]==1000000000)
        {
            printf("0 ");
        }
        else
            {printf("%d ",d[i]);}
    }
    fclose(stdout);
    return 0;
}