//fara heap
#include <stdio.h>
#define inf 1<<30
typedef struct nod
{
    int val,cost;
    nod *urm;
} adr;

adr *L[50000],*p;
int D[50000],n,m,i,j,c,k,poz,min;
short int E[50000];

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->urm=L[i];
        p->cost=c;
        L[i]=p;
    }
    p=L[1];
    while (p)
    {
        D[p->val]=p->cost;
        p=p->urm;
    }
    for (i=1; i<=n; i++) if (!D[i]) D[i]=inf;
    for (i=1; i<n; i++)
    {
        min=inf;
        for (j=2; j<=n; j++)
            if (!E[j])
                if (D[j]<min)
                {
                    min=D[j];
                    poz=j;
                }
        E[poz]=1;
        for (j=2; j<=n; j++)
            if (!E[j])
            {
                p=L[poz];
                while (p && p->val!=j) p=p->urm;
                if (p)
                {
                    if (D[poz]+p->cost<D[j]) D[j]=D[poz]+p->cost;
                }
            }

    }
    for (i=2; i<=n; i++) printf("%d ",D[i]);

    return 0;
}