#include<stdio.h>
int a,b,cost,start[50001],t[3][250001],m,n,infinit=1000000001;
void citire()
{
    int k=0,i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&cost);
        ++k;
        t[0][k]=b;
        t[1][k]=start[a];
        t[2][k]=cost;
        start[a]=k;
    }
}
void dijkstra(int vf)
{
    int viz[50002],i,j,vmin,d[50002],poz;
    for(i=1;i<=n;i++)
    {
        viz[i]=0;
        d[i]=infinit;
    }
    d[vf]=0;
    for(i=1;i<=n;i++)
    {
        vmin=infinit;
        for(j=1;j<=n;j++)
            if(viz[j]==0 && d[j]<vmin)
            {
                vmin=d[j];
                poz=j;
            }
        if(vmin==infinit) break;
        viz[poz]=1;
        for(j=start[poz];j;j=t[1][j])
        {
            if(d[t[0][j]]>d[poz]+t[2][j] && viz[t[0][j]]==0)
            {
                d[t[0][j]]=d[poz]+t[2][j];            }
        }
    }
    //
    for(i=2;i<=n;i++)
        {
            if(d[i]==infinit) printf("0 ");
            else printf("%d ",d[i]);
        }
}
int main()
{

    freopen("dijkstra.in","rt",stdin);
    freopen("dijkstra.out","wt",stdout);
    citire();
    dijkstra(1);
    fclose(stdout);
    return 0;
}