//fara heap
#include <cstdio>
#define inf 0x7fffffff
#define N 50001

typedef struct noduri
{
    int val,cost;
    noduri *urm;
} adr;

adr *L[N],*p;
int C[N],E[N],n,m,i,j,c,k,nod,min;

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for (k=1; k<=m; k++)
    {
        scanf("%d %d %d\n",&i,&j,&c);
        p=new adr;
        p->val=j; p->cost=c;
        p->urm=L[i];
        L[i]=p;
    }
    p=L[1];
    for (p=L[1]; p; p=p->urm) C[p->val]=p->cost;
    for (i=2; i<=n; i++) if (!C[i]) C[i]=inf;

    for (i=1; i<n; i++)
    {
        min=inf;
        for (j=2; j<=n; j++)
            if (!E[j] && C[j]<min)
            {
                min=C[j];
                nod=j;
            }
        E[nod]=1;
        for (p=L[nod]; p; p=p->urm)
            if (min+p->cost<C[p->val])
                C[p->val]=min+p->cost;
    }

    for (i=2; i<=n; i++)
        if (C[i]<inf) printf("%d ",C[i]);
        else          printf("0 ");


    return 0;
}