#include <stdio.h>
#include <stdlib.h>

#define Maxx 10000

int main()
{
    int **t, n, m, x, y,z, *ut, * latott, *apa, mini, poz;
    // freopen("be.txt","r",stdin);
    scanf("%d%d",&n,&m);

    t = (int **) calloc(n+1,sizeof(int *));
    ut = (int * ) calloc(n+1,sizeof(int));
    latott = (int * ) calloc(n+1,sizeof(int));
    apa = (int * ) calloc(n+1,sizeof(int));

    for (int i = 0 ; i<=n ; i++)
        t[i] = (int *) calloc(n+1,sizeof(int));


    for (int i = 1; i<n ; i++)
        for (int j = i+1 ; j<=n ; j++)
            t[i][j] = Maxx;


    for (int i = 0 ; i<m ; i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        t[x][y] =  z;
    }
    /*
        for (int i = 1 ; i<=n ; i++)
        {
            for (int j = 1; j<=n ; j++)
                printf("%d ",t[i][j]);
            printf("\n");
        }
        */
    int kezd = 1;

    for (int i = 1; i<=n ; i++)
    {
        ut[i] = t[kezd][i];
        apa[i] = kezd;
    }
    latott[kezd] = 1;

    for (int i = 1 ; i<=n ; i++)
    {
        mini = Maxx;
        for (int j = 1 ; j<=n ; j++)
            if (!latott[j] && ut[j]<mini)
            {
                mini = ut[j];
                poz = j;
            }
        for (int k = 1 ; k<=n ; k++)
            if (!latott[k] && t[poz][k]!=Maxx)
                if (ut[k] > t[poz][k] + ut[poz])
                {
                    ut[k] = t[poz][k] + ut[poz];
                    apa[k] = poz;
                }
        latott[poz] = 1;
    }
    /*
        for (int i = 2; i<=n ; i++)
            printf("%d.pont\t%d tavolsagra van %d tol \t %d pontbol erkeztunk\n",i,ut[i],kezd,apa[i]);
    */
    for (int i = 2; i<=n ; i++)
        printf("%d ",ut[i]);
}