#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#define maxN 50005
#define PB push_back
#define MKP make_pair
#define inf (1 << 30)

int N, M, dimH;
int cost[maxN], H[maxN], pozH[maxN], viz[maxN];
vector < pair <int, int> > list[maxN];


void push(int nod) {
    if(nod == 1) return;
    if(cost[H[nod]] >= cost[H[nod / 2]]) return;

    swap(H[nod], H[nod / 2]);
    swap(pozH[H[nod]], pozH[H[nod / 2]]);

    push(nod / 2);
}

void pop(int nod) {
    int f1 = nod * 2, f2 = nod * 2 + 1;
    int nodmin = nod;

    if(f1 <= dimH && cost[H[f1]] < cost[H[nodmin]]) nodmin = f1;
    if(f2 <= dimH && cost[H[f2]] < cost[H[nodmin]]) nodmin = f2;

    if(nod == nodmin) return;

    swap(H[nod], H[nodmin]);
    swap(pozH[H[nod]], pozH[H[nodmin]]);

    pop(nodmin);
}

int main() {
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");

    f >> N >> M;

    while(M --) {
        int x, y, c;
        f >> x >> y >> c;

        list[x].PB(MKP(y, c));
    }

    H[++ dimH] = 1;
    pozH[1] = 1;

    for(int i = 2; i <= N; ++ i) {
        cost[i] = inf;
        H[++ dimH] = i;
        pozH[i] = i;
    }

    for(int i = 1; i <= N; ++ i) {
        int nod = H[1];
        viz[nod] = true;

        swap(H[1], H[dimH]);
        swap(pozH[H[1]], pozH[H[dimH]]);
        -- dimH;
        pop(1);

        for(unsigned int j = 0; j < list[nod].size(); ++ j) {
            int nod2 = list[nod][j].first, cost2 = list[nod][j].second;

            if(cost[nod2] <= cost[nod] + cost2) continue;
            if(viz[nod2]) continue;

            cost[nod2] = cost[nod] + cost2;

            int pozH2 = pozH[nod2];

            if(cost[H[pozH2]] <= cost[H[pozH2 / 2]]) push(pozH2);
            else pop(pozH2);
        }
    }

    for(int i = 2; i <= N; ++ i)
        if(cost[i] == inf) {
            g << "0 ";
        } else {
            g << cost[i] << " ";
        }

    return 0;
}