#include <stdio.h>
#include <string.h>
#define max 50010
const int inf=0x3f3f3f3f;
struct lista
{
    int nod,cost;
    lista *next;
};
lista *g[max],*p;
int d[max],q[max*5],i,j,n,m,k,c,ultim,prim,u,w;
char inq[max*5];
void push(int i,int j,int c)
{
    lista *p=new lista;
    p->nod=j;
    p->cost=c;
    p->next=g[i];
    g[i]=p;
}
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,&c);
        push(i,j,c);
    }
    memset(d,inf,sizeof(d));
    d[1]=0;
    q[1]=prim=ultim=1; inq[1]=1;
    while(prim<=ultim)
    {
        u=q[prim++];
        inq[u]=0;
        for(p=g[u]; p!=NULL; p=p->next)
        {
            w=p->nod;
            if(d[p->nod]>d[u]+p->cost)
             {
                if(!inq[w])
                 {
                   inq[w]=1;
                   q[++ultim]=w;
                 }
               d[w]=d[u]+p->cost;
             }
       }
    }
    for(i=2; i<=n; i++)
     if(d[i]==inf) printf("0 ");
     else printf("%d ",d[i]);
    return 0;
}