#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];
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;
    }
    viz[1]=1;
    d[1]=0;
    for(p=v[1];p!=0;p=p->adr)
    {
        d[p->vecin]=p->cost;
        t[p->vecin]=1;
    }
    for(k=1;k<=N-1;k++)
    {
        vmin=1000000000;
        for(i=1;i<=N;i++)
        {
            if(viz[i]==0 && d[i]<vmin)
            {
                x=i;
                vmin=d[i];
            }
        }
        viz[x]=1;
        for(p=v[x];p!=0;p=p->adr)
        {
            if(d[p->vecin]>p->cost+d[x] && viz[p->vecin]==0)
            {
                d[p->vecin]=p->cost+d[x];
                t[p->vecin]=x;
            }
        }
    }
    for(i=2;i<=N;i++)
    {
        if(d[i]==1000000000)
        {
            printf("0 ");
        }
        else
            {printf("%d ",d[i]);}
    }
    fclose(stdout);
    return 0;
}