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

#define NMAX 50000
#define MMAX 250000

static unsigned adj_list[NMAX+1], d[NMAX+1], ch[NMAX];
static unsigned char in_ch[NMAX+1];

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

int main(void)
{
    unsigned n, i, m, j, cht, chh;

    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);

    cht = chh = 0;
    d[1] = 0;
    ch[cht++] = 1;
    in_ch[1] = 1;

    while (chh != cht) {
        in_ch[ch[chh]] = 0;

        for (j = adj_list[ch[chh]]; j != 0; j = edges[j].n) {
            if (edges[j].w + d[edges[j].u] < d[edges[j].v]) {
                d[edges[j].v] = edges[j].w + d[edges[j].u];

                if (!in_ch[edges[j].v]) {
                    in_ch[edges[j].v] = 1;

                    ch[cht++] = edges[j].v;

                    cht = cht == NMAX ? 0 : cht;
                }
            }
        }

        chh++;
        chh = chh == NMAX ? 0 : chh;
    }

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

    return 0;
}