#include <stdio.h>
#define max 100010
struct lista
{
    int nod,cost;
    lista *next;
};
lista *g[max],*p;
int q[max],d[max],n,m,i,j,c,u,ultim,prim;
char inq[max];
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(; m--; )
    {
        scanf("%d%d%d",&i,&j,&c);
        p=new lista; p->nod=j; p->cost=c;
        p->next=g[i]; g[i]=p;
    }
    for(i=1; i<=n; i++) d[i]=max;

    d[1]=0; q[0]=1;
    while(prim<=ultim)
    {
        u=q[prim++];
        inq[u]=0;
        for(p=g[u]; p!=NULL; p=p->next)
         if(d[p->nod]>d[u]+p->cost)
         {
             if(!inq[p->nod])
             {
                 inq[p->nod]=1;
                 q[++ultim]=p->nod;
             }
             d[p->nod]=d[u]+p->cost;
         }
    }
    for(i=2; i<=n; i++)
     if(d[i]==max) printf("0 ");
     else printf("%d ",d[i]);
    return 0;
}