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

#define INF 2000000001
#define NMax 50005

typedef struct lista { int idd, cost; struct lista *next; };
typedef lista *Graf[NMax];

int N, M, H[NMax], el, dist[NMax], poz[NMax];
Graf G;

void add_to_list(lista **l, int item, int cst)
{
    lista *tmp = (lista *)malloc(sizeof(lista));

    tmp->idd = item;
    tmp->cost = cst;
    tmp->next = *l;
    *l = tmp;
}

void swap(int &a, int &b)
{
    int poz = a;
    a = b;
    b = poz;
}

void sift(int nod)
{
    int imin;

    for (; 2 * nod <= el; )
    {
        imin = 2 * nod;
        if (2 * nod + 1 <= el && dist[H[2*nod]] > dist[H[2*nod+1]])
            imin = 2*nod+1;

        if (dist[H[nod]] > dist[H[imin]])
            swap(poz[H[nod]], poz[H[imin]]),
            swap(H[nod], H[imin]),
            nod = imin;
        else
            return ;
    }
    
}

void percolate(int nod)
{
    for (; nod > 1; nod >>= 1)
        if (dist[H[nod]] < dist[H[nod>>1]])
            swap(poz[H[nod]], poz[H[nod>>1]]),
            swap(H[nod], H[nod>>1]);
        else
            return ;
}

int main(void)
{
    int i, j, c;
    lista *f;
    
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    scanf("%d %d", &N, &M);
    for (; M; --M)
    {
        scanf("%d %d %d", &i, &j, &c);
        add_to_list(&G[i], j, c);
    }

    for (i = 1; i <= N; ++i)
        dist[i] = INF, H[++el] = i, poz[i] = i;
    dist[1] = 0;
    
    for (i = 1; i < N; ++i)
    {
        j = H[1];
        H[1] = H[el--]; poz[H[1]] = 1; sift(1);

        if (dist[j] == INF)
            continue;

        for (f = G[j]; f; f = f->next)
            if (dist[j] + f->cost < dist[f->idd])
            {
                dist[f->idd] = dist[j] + f->cost;
                percolate(poz[f->idd]);
            }
    }

    for (i = 2; i <= N; ++i)
        printf("%d ", (dist[i] == INF) ? (0) : (dist[i]));
    printf("\n");

    return 0;
}