#include <fstream>

using namespace std;

const int MAX_N = 50000;
const int MAX_M = 250000;
const int INF = 1000000000;
const int NIL = -1;

struct Arc {
    int v, weight;
    int next;
};

Arc G[MAX_M];
int head[MAX_N];

int D[MAX_N];

int H[MAX_N];
int heapPos[MAX_N];
int heapSize;

void addArc(int u, int v, int weight, int pos) {
    G[pos].v = v;
    G[pos].weight = weight;
    G[pos].next = head[u];
    head[u] = pos;
}

void downHeap(int u) {
    int best, changed;

    do {
        best = u;
        changed = 0;
        for (int i = 1; i <= 2; ++ i) {
            if (2 * u + i < heapSize && D[H[2 * u + i]] < D[H[best]]) {
                best = 2 * u + i;
            }
        }
        if (best != u) {
            changed = 1;
            heapPos[H[best]] = u;
            heapPos[H[u]] = best;
            swap(H[u], H[best]);
            u = best;
        }
    } while (changed);
}

void upHeap(int u) {
    int father = (u - 1) / 2;

    while (u > 0 && D[H[father]] > D[H[u]]) {
        heapPos[H[u]] = father;
        heapPos[H[father]] = u;
        swap(H[u], H[father]);
        u = father;
        father = (u - 1) / 2;
    }
}

int main() {
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin.tie(0);
    ios_base::sync_with_stdio(false);

    int N, M; fin >> N >> M;

    for (int i = 0; i < N; ++ i) {
        head[i] = NIL;
    }
    for (int i = 0; i < M; ++ i) {
        int u, v, weight; fin >> u >> v >> weight;
        addArc(u - 1, v - 1, weight, i);
    }

    for (int i = 1; i < N; ++ i) {
        D[i] = INF;
        H[i] = i;
        heapPos[i] = i;
    }

    D[0] = 0;
    heapSize = N;

    while (heapSize && D[H[0]] != INF) {
        int u = H[0];

        H[0] = H[--heapSize];
        downHeap(0);

        for (int i = head[u]; i != NIL; i = G[i].next) {
            int v = G[i].v;

            if (D[v] > D[u] + G[i].weight) {
                D[v] = D[u] + G[i].weight;
                upHeap(heapPos[v]);
            }
        }
    }

    for (int i = 1; i < N; ++ i) {
        fout << ((D[i] == INF) ? 0 : D[i]) << " \n"[i == N - 1];
    }
    fout.close();

    return 0;
}