#include <fstream>
#include <vector>

#define MaxN 50005
#define Inf 123456789

using namespace std;

struct Graf {
    int to, cost;

    Graf(int to, int cost) : to(to), cost(cost) { }
};

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int N, M, D[MaxN], poz[MaxN], heap[MaxN], heap_size;
vector<Graf> G[MaxN];

void heapswap(int x, int y) {
    int temp = heap[x];
    heap[x] = heap[y];
    heap[y] = temp;
}

void upheap(int index) {
    while (index > 1) {
        int parentIndex = index / 2;

        if (D[heap[parentIndex]] > D[heap[index]]) {
            poz[heap[parentIndex]] = index;
            poz[heap[index]] = parentIndex;

            heapswap(parentIndex, index);

            index = parentIndex;
        } else
            break;
    }
}

void downheap(int index) {
    if (index > heap_size) return;

    int minIndex = index;

    if (2 * index <= heap_size && D[heap[index]] > D[heap[2 * index]]) {
        minIndex = 2 * index;
    }

    if (2 * index + 1 <= heap_size && D[heap[minIndex]] > D[heap[2 * index + 1]]) {
        minIndex = 2 * index + 1;
    }

    if (minIndex != index) {
        poz[heap[minIndex]] = index;
        poz[heap[index]] = minIndex;

        heapswap(minIndex, index);

        downheap(minIndex);
    }
}

int main()
{
    fin >> N >> M;
    for (int m = 1; m <= M; ++m) {
        int x, y, c;
        fin >> x >> y >> c;
        G[x].push_back(Graf(y, c));
    }

    for (int i = 2; i <= N; ++i) {
        D[i] = Inf;
        poz[i] = -1;
    }

    heap[1] = 1;
    heap_size = 1;
    poz[1] = 1;

    while (heap_size > 0) {
        int mymin = heap[1];
        heapswap(1, heap_size);
        --heap_size;

        poz[heap[1]] = 1;

        downheap(1);

        for (int index = 0; index < G[mymin].size(); ++index) {
            Graf node = G[mymin][index];

            if (D[mymin] + node.cost < D[node.to]) {
                D[node.to] = D[mymin] + node.cost;

                if (poz[node.to] != -1) {
                    upheap(poz[node.to]);
                } else {
                    ++heap_size;
                    heap[heap_size] = node.to;
                    poz[node.to] = heap_size;

                    upheap(heap_size);
                }
            }
        }
    }

    for (int i = 2; i <= N; ++i) {
        fout << ((D[i] == Inf) ? 0 : D[i]) << ' ';
    }

    return 0;
}