#include <cstdio>
#include <cstdlib>
#define inf (50000001)

struct muchie{
    int x,cst;
    struct muchie *next;} *nod[50002];
int n,m,dst[50002];

void init()
{   int i;
    for(i=1;i<=n;i++)
    {nod[i]=new muchie;
     nod[i]->next=NULL;
     nod[i]->x=0;
     dst[i]=inf;};
}

void make()
{   struct muchie *a,*b,*c,*d;
    dst[1]=0;
    a=new muchie;
    a->x=1;
    a->cst=0;
    a->next=NULL;
    b=a;
    while(a!=NULL){
        c=nod[a->x];
        while(c->x!=0){
        if(a->cst+c->cst<dst[c->x])
        {dst[c->x]=a->cst+c->cst;
         d=new muchie;
         d->x=c->x;
         d->cst=dst[c->x];
         d->next=NULL;
         b->next=d;
         b=d;};
        c=c->next;};
        c=a;a=a->next;delete c;};
}

int main()
{   int i,x,y,cst;
    struct muchie *a;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    init();
    for(i=1;i<=m;i++)
    {scanf("%d%d%d",&x,&y,&cst);
     a=new muchie;
     a->x=y;
     a->cst=cst;
     a->next=nod[x];
     nod[x]=a;};
    make();
    for(i=2;i<=n;i++)
    if(dst[i]==inf)printf("%d ",0);else printf("%d ",dst[i]);
    return 0;
}