#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

const int M = 25e4, N = 5e4;
const int INF = 1e9;

struct MinHeap {
    int num_added = 0;
    pii heap[M + 1];

    // - helper functions
    inline bool has_vertices () {
        return num_added >= 1;
    }
    inline int get_parent (int v) {
        return (v >> 1);
    }
    inline int get_left_child (int v) {
        return (v << 1);
    }
    inline int get_right_child (int v) {
        return (v << 1) + 1;
    }
    inline bool relationship_holds (pii p, pii c) {
        return p.second <= c.second;
    }
    // ---

    inline pii get_min () {
        if (num_added >= 1) {
            return heap[1];
        }
        return {-1, -1};
    }

    inline void add (pii a) {
        num_added++;
        heap[num_added] = a;

        int v = num_added;
        while (v>1) {

            // - bad parent-child relationship
            int p = get_parent(v);
            if (!relationship_holds(heap[p], heap[v])) {
                swap(heap[v], heap[p]);
                v = p;
            } else {
                break;
            }
        }
    }

    inline void pop () {
        // - remove the root
        if (num_added < 1) {
            return;
        }

        swap(heap[num_added], heap[1]);
        heap[num_added] = {INF, INF};
        num_added--;

        int v = 1;
        while (true) {
            int lc = get_left_child(v);
            int rc = get_right_child(v);

            // - we reached a leaf
            if (lc > num_added && rc > num_added) {
                break;
            }

            int min_child = -1;
            if (lc <= num_added) {
                min_child = lc;
            }
            if (rc <= num_added) {
                if (min_child == -1) {
                    min_child = rc;
                } else if (heap[rc] < heap[min_child]) {
                    min_child = rc;
                }
            }

            // - bad parent-child relationship
            if (!relationship_holds(heap[v], heap[min_child])) {
                swap(heap[v], heap[min_child]);
                v = min_child;
            } else {
                break;
            }
        }
    }
};

MinHeap h;
int d[N + 1];
vector<pair<int, int>> adj[N + 1];

int main () {
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");

    int n, m, u, v, w;

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }

    for (int i = 1; i <= n; i++) {
        d[i] = INF;
    }

    d[1] = 0;
    h.add({1, d[1]});

    while (h.has_vertices()) {
        auto [u, dist] = h.get_min();
        // cout << "we reached " << u << " with best distance: " << dist << "\n";
        // cout << u << " " << dist << "\n";
        h.pop();

        if (dist > d[u]) {
            continue;
        }

        for (auto [v, w] : adj[u]) {
            int new_d = dist + w;
            // scout << "> we can reach " << v << " from " << u << " w/: " << new_d << "\n";
            if (new_d < d[v]) {
                d[v] = new_d;
                h.add({v, d[v]});
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        if (d[i] == INF) {
            // - if there does not exist a path
            d[i] = 0;
        }
        cout << d[i] << " ";
    }
    return 0;
}

/*
7 9
1 4 2
1 2 1
2 3 3
4 3 1
3 5 2
5 6 5
6 3 1
3 7 2
1 5 9
*/