#include <stdio.h>
#define max 50001
const int inf=1<<30;
struct graf
{
    int nod,cost;
    graf *urm;
};
graf *a[max],*p;
int d[max],n,m,i,j,k,min,pmin;
char q[max];
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(; m>0; m--)
    {
        scanf("%d%d%d",&i,&j,&k);
        p=new graf;
        p->cost=k;
        p->nod=j;
        p->urm=a[i];
        a[i]=p;
    }
    for(i=2; i<=n; i++) d[i]=inf;
    for(i=1; i<=n; i++)
    {
        min=inf;
        for(j=1; j<=n; j++)
         if(!q[j] && min>d[j])
          min=d[j],pmin=j;
        q[pmin]=1;
        p=a[pmin];
        while(p)
        {
            if(d[p->nod]>d[pmin]+p->cost)
             d[p->nod]=d[pmin]+p->cost  ;
            p=p->urm;
        }
    }
    for(i=2; i<=n; i++)
     if(d[i]!=inf) printf("%d ",d[i]);
     else printf("0 ");
    return 0;
}