#include <stdio.h>
#include <string.h>

#define NMAX 50000
#define MMAX 250000

static unsigned adj_list[NMAX+1], d[NMAX+1];
static unsigned node_to_heap[NMAX+1], hsize;

static struct edge {
    unsigned u, v, w, n;
} edges[MMAX+1];

static struct h_elem {
    unsigned n, key;
} heap[NMAX+1];

static void h_insert(unsigned n)
{
    ++hsize;
    heap[hsize].n = n;
    heap[hsize].key = 0xFFFFFFFF;
    node_to_heap[n] = hsize;
}

static struct h_elem h_extract_min(void)
{
    unsigned i, i_min;

    struct h_elem min = heap[1], aux;
    heap[1] = heap[hsize];
    node_to_heap[heap[1].n] = 1;
    hsize--;

    i = 1;
    while (i < hsize) {
        i_min = i;

        if (2 * i <= hsize && heap[2 * i].key < heap[i_min].key) {
            i_min = 2 * i;
        }

        if (2 * i + 1 <= hsize && heap[2 * i + 1].key < heap[i_min].key) {
            i_min = 2 * i + 1;
        }

        if (i == i_min) {
            break;
        }

        node_to_heap[heap[i].n] = i_min;
        node_to_heap[heap[i_min].n] = i;

        aux = heap[i];
        heap[i] = heap[i_min];
        heap[i_min] = aux;
        i = i_min;
    }

    return min;
}

static void h_update(unsigned n, unsigned key)
{
    struct h_elem aux;
    unsigned i = node_to_heap[n];
    heap[i].key = key;

    while (i > 1 && heap[i / 2].key >= heap[i].key) {
        node_to_heap[heap[i].n] = i / 2;
        node_to_heap[heap[i / 2].n] = i;

        aux = heap[i];
        heap[i] = heap[i / 2];
        heap[i / 2] = aux;
        i /= 2;
    }
}

int main(void)
{
    struct h_elem min;
    unsigned n, i, m;

    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

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

    for (i = 1; i <= m; i++) {
        scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);
        edges[i].n = adj_list[edges[i].u];
        adj_list[edges[i].u] = i;
    }

    memset(d, 0xFF, sizeof d);

    for (i = 1; i <= n; i++) {
        h_insert(i);
    }

    h_update(1, 0);
    d[1] = 0;

    while (hsize) {
        min = h_extract_min();
        d[min.n] = min.key;

        for (i = adj_list[min.n]; i != 0; i = edges[i].n) {
            if (d[min.n] + edges[i].w < d[edges[i].v]) {
                d[edges[i].v] = d[min.n] + edges[i].w;
                h_update(edges[i].v, d[min.n] + edges[i].w);
            }
        }
    }

    for (i = 2; i <= n; i++) {
        printf("%u%c", d[i] == 0xFFFFFFFF ? 0 : d[i], " \n"[i == n]);
    }

    return 0;
}