#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define LMAX 50010
#define INF (~(1<<31))

struct Muchie {
    int n, c;
    Muchie() {n=c=0;};
    Muchie(int nod, int cost) {
        n = nod;
        c = cost;
    }
};

int N, M, L;
int C[LMAX], heap[LMAX];
int poz[LMAX];
vector<Muchie> V[LMAX];

void citire() {
    scanf("%d %d", &N, &M);
    for (int x,y,c; M; --M) {
        scanf("%d %d %d", &x, &y, &c);
        V[x].push_back(Muchie(y,c));
    }
}

int heap_pop () {
    int min = heap[1];
    swap(heap[1], heap[L]);
    poz[heap[1]] = 1;
    --L;

    int ch, p=1;
    while (p <= L) {
        ch = p<<1;
        if (ch <= L) {
            if (ch+1 <= L && C[heap[ch+1]] < C[heap[ch]])
                ++ch;
        } else break;

        if (C[heap[ch]] > C[heap[p]]) {
            poz[heap[ch]] = p;
            poz[heap[p]] = ch;
            swap(heap[ch], heap[p]);
            p = ch;
        } else break;
    }

    return min;
}

void heap_push(int ch) {
    int p;
    while (ch>1) {
        p = ch>>1;
        if (C[heap[p]] > C[heap[ch]]) {
            poz[heap[p]] = ch;
            poz[heap[ch]] = p;
            swap(heap[p],heap[ch]);
            p = ch;
        } else break;
    }
}

void dijkstra() {
    for (int i=2; i<=N; ++i)
        C[i] = INF;

    heap[++L] = 1;
    poz[1] = L;
    Muchie nod;

    int min;
    while (L) {
        min = heap_pop();
        for (int i=0, e=V[min].size(); i<e; ++i) {
            nod = V[min][i];
            if (C[nod.n] > C[min] + nod.c) {
                C[nod.n] = C[min] + nod.c;

                if (poz[nod.n]) heap_push(poz[nod.n]);
                else {
                    heap[++L] = nod.n;
                    poz[nod.n] = L;
                    heap_push(L);
                }
            }
        }
    }
}

int main () {

    freopen("dijkstra.in","rt",stdin);
    freopen("dijkstra.out","wt",stdout);

    citire();
    dijkstra();
    for (int i=2; i<=N; ++i)
        printf("%d ", (C[i] == INF)? 0: C[i]);

    return 0;
}