#include<stdio.h>
using namespace std;
 struct arc
{
    int x;
    int y;
    int c;
}v[250001];
int n,m,i,j,X,Y,cost;
int inf=10000,dmin,vmin;
int p[50001],d[50001],s[50001];
 
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d %d",&n,&m);
         
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d",&X,&Y,&cost);
        v[i].x=X;
        v[i].y=Y;
        v[i].c=cost;
    }
     
    for(i=1;i<=n;i++)
    {
        p[i]=0;
        d[i]=inf;
        s[i]=0;
    }
    s[1]=1;
    for(i=1;i<=m;i++)
    {
        if(v[i].x==1)
        {
            d[v[i].y]=v[i].c;
            p[v[i].y]=1;
        }
    }
             
         
     
    for(j=1;j<=n;j++)
    {
        dmin=inf;
        vmin=0;
        for(i=1;i<=n;i++)
            if(s[i]==0 && d[i]<dmin)
            {
                dmin=d[i];
                vmin=i;
            }
        if(vmin!=0)
        {
            s[vmin]=1;
            for(i=1;i<=m;i++)
            {
                if(v[i].x==vmin)
                    if(d[v[i].y]>d[vmin]+v[i].c)
                    {
                        d[v[i].y]=d[vmin]+v[i].c;
                        p[i]=vmin;
                    }
            }
        }
    }
    for(i=2;i<=n;i++)
        printf("%d ",d[i]);
    printf("\n");
 
    return 0;
}