#include <stdio.h>

    #define inf 1<<30

    #define maxn 50005

    struct NOD 

    { int info,cost;

    NOD *urm;};

    int x,n,m,i,j,min;

    int H[maxn];

    int D[maxn];

    int poz[maxn];

    NOD *list[maxn];

    NOD *urm;

     

    void shift(int x,int n)

    {

    int tata,v,fiu;

    tata = x; fiu=x<<1; v=H[x];

     

    while (fiu<=n)

    {

    if (fiu<n)

    if (D[H[fiu]]>D[H[fiu+1]]) fiu++;

    if (D[v]>D[H[fiu]])

    {

    H[tata] = H[fiu];

    poz[H[tata]] = tata;

    tata = fiu;

    fiu = tata << 1;

    }

    else fiu = n+1;

    }

    H[tata] = v;

    poz[v] = tata;

    }

     

    void up(int i,int n)

    {

    int tata,fiu,aux;

    fiu = i;

    tata = i>>1;

    while (tata!=0 && D[H[tata]]>D[H[fiu]])

    {

    poz[H[tata]] = fiu;

    poz[H[fiu]] = tata;

    aux = H[tata];

    H[tata] = H[fiu];

    H[fiu] = aux;

    fiu = tata;

    tata = fiu >> 1;

    }    

    }    

     

    int main()

    {

    freopen("dijkstra.in","r",stdin);

    freopen("dijkstra.out","w",stdout);

     

    scanf("%d%d",&n,&m);

     

    for (;m;m--)

    {

    urm = new NOD;

    scanf("%d%d%d",&x,&urm->info,&urm->cost);

    urm->urm = list[x];

    list[x] = urm;

    }

     

    for (i=1;i<=n;i++)

    {

    H[i] = i;

    poz[i] = i;

    D[i] = inf;

    }

     

    urm = list[1];

    while (urm!=NULL)

    {

    D[urm->info] = urm->cost;

    urm = urm->urm;

    }

     

    for (i=n>>1;i>0;i--) shift(i,n);

     

    for (i=n;i>0;i--)

    {

    min = H[1];

    H[1]=H[i];

    shift(1,i-1);

    urm = list[min];

    while (urm!=NULL)

    {

    if (D[urm->info]>D[min]+urm->cost)

    {

    D[urm->info] = D[min]+urm->cost;

    up(poz[urm->info],i-1);

    }

    urm = urm->urm;

    } 

    }

    for (i=2;i<=n;i++)

    if (D[i]==inf) printf("0 ");

    else printf("%d ",D[i]);

     

    }