#include<stdio.h>
int v[250010][3],c[50010],i,x,y,j,ok;
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d %d",&x, &y);
    for(i=2;i<=x;i++)c[i]=2000000000;
    for(i=1;i<=y;i++)
    {  
        scanf("%d %d %d",&v[i][0],&v[i][1],&v[i][2]);
        if(v[i][0]==1)c[v[i][1]]=v[i][2];
    }
    while(!ok)
    {
        ok=1;
        for(j=1;j<=y;j++)
        {   
            if(c[v[j][1]]>c[v[j][0]]+v[j][2])
                {
                    c[v[j][1]]=c[v[j][0]]+v[j][2];
                    ok=0;
                }
        }
    }
    for(i=2;i<=x;i++)
       if(c[i]<2000000000)printf("%d ",c[i]);
        else printf("0 ");
    return 0;
}