#include <cstdio>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;

#define Nmax 50010
#define INF 0x3f3f3f3f

int n, m, N;
int Cst[Nmax], H[Nmax], Poz[Nmax];
vector < pair <int, int> > V[Nmax];

void citire () {

    int i, x, y, z;

    scanf ("%d %d", &n, &m);
    for (i = 1; i <= m; i++) {
        scanf ("%d %d %d", &x, &y, &z);
        V[x].push_back ( make_pair (y, z));
    }
}

void up_heap (int poz) {

    int t, c = poz, aux;
    t = c >> 1;

    while (t && Cst[ H[t] ] > Cst[ H[c] ]) {
        aux = H[t];
        H[t] = H[c];
        H[c] = aux;

        Poz[H[t]] = t;
        Poz[H[c]] = c;

        c = t; t = c >> 1;
    }
}

void down_heap (int poz) {

    int t = poz, c, aux;
    c = t << 1;
    if (c < N && Cst[ H[c + 1] ] < Cst[ H[c] ] ) c++;

    while (c <= N && Cst[ H[t] ] > Cst[ H[c] ]) {
        aux = H[t];
        H[t] = H[c];
        H[c] = aux;

        Poz[H[t]] = t;
        Poz[H[c]] = c;

        t = c;
        c = t << 1;
        if (c < N && Cst[ H[c + 1] ] < Cst[ H[c] ] ) c++;
    }
}

void dijkstra () {

    int i, nod;
    vector < pair<int, int> >::iterator it;

    memset (Cst, INF, sizeof (Cst));
    Cst[1] = 0;
    H[++N] = 1; Poz[1] = 1;

    for (i = 1; N; i++) {
        nod = H[1];
        H[1] = H[N]; N--;
        Poz[ H[1] ] = 1;
        down_heap (1);

        for (it = V[nod].begin (); it != V[nod].end (); it++)
            if (Cst[it->first] > Cst[nod] + it->second) {
                Cst[it->first] = Cst[nod] + it->second;
                if (Poz[it->first] == 0) {
                    H[++N] = it->first;
                    Poz[ H[N] ] = N;
                }

                up_heap (Poz[it->first]);
            }
    }

    for (i = 2; i <= n; i++) {
        if (Cst[i] == INF) Cst[i] = 0;
        printf ("%d ", Cst[i]);
    }
}

int main () {

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

    citire ();
    dijkstra ();

    return 0;
}