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

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

void down(int tata, int n)
{
    int t,fiu;
    fiu=tata<<1;
    if (D[H[fiu+1]]<D[H[fiu]]) fiu++;
    while (fiu<=n && D[H[tata]]>D[H[fiu]])
    {
        t=H[fiu]; H[fiu]=H[tata]; H[tata]=t;
        tata=fiu; fiu<<=1;
    }
}

void up(int fiu)
{
    int t,tata=fiu>>1;
    while (tata && D[H[tata]]>D[H[fiu]])
    {
        t=H[fiu]; H[fiu]=H[tata]; H[tata]=t;
        fiu=tata; tata>>=1;
    }
}


void heap()
{
    for (int i=n>>1; i; i--) down(i,n);
}

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];
    H[n+1]=inf;
    while (p)
    {
        D[p->val]=p->cost;
        p=p->urm;
    }
    //heap-ul
    for (i=1; i<=n; i++)
    {
        H[i]=i;
        if (!D[i]) D[i]=inf;
    }
    heap();
    //dijkstra
    for (i=1; i<n; i++)
    {
        poz=H[1];
        H[1]=H[n-i+1];
        down(1,n-i+1);
        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;
                    up(j);
                }
            }
    }
    for (i=2; i<=n; i++)
        if (D[i]>=inf) printf("0 ");
        else printf("%d ",D[i]);

    return 0;
}