#include <bits/stdc++.h>

using namespace std;

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

// heap binar indexat: pastram pozitia fiecarui nod in heap, ca sa putem face decrease_key in O(log n)
class IndexedHeap {
    vector<pair<int, int>> a; // {dist, node}
    vector<int> pos;          // pos[node] = pozitia in heap, -1 daca nodul nu e in heap

    void swap_nodes(int i, int j) {
        swap(a[i], a[j]);
        pos[a[i].second] = i;
        pos[a[j].second] = j;
    }

    void heapify_up(int i) {
        while (i > 0) {
            int p = (i - 1) / 2;
            if (a[p].first <= a[i].first) break;

            swap_nodes(p, i);
            i = p;
        }
    }

    void heapify_down(int i) {
        int n = a.size();
        while (true) {
            int l = 2 * i + 1, r = 2 * i + 2, sm = i;
            if (l < n && a[l].first < a[sm].first) sm = l;
            if (r < n && a[r].first < a[sm].first) sm = r;
            if (sm == i) break;

            swap_nodes(sm, i);
            i = sm;
        }
    }

public:
    void init(int n) {
        pos.assign(n + 1, -1);
        a.clear();
    }

    bool empty() {
        return a.empty();
    }

    bool contains(int node) {
        return pos[node] != -1;
    }

    void push(int node, int dist) {
        a.push_back({dist, node});
        pos[node] = a.size() - 1;
        heapify_up(a.size() - 1);
    }

    void decrease_key(int node, int new_dist) {
        int i = pos[node];
        a[i].first = new_dist;
        heapify_up(i);
    }

    pair<int, int> extract_min() {
        pair<int, int> rez = a[0];
        pos[rez.second] = -1;

        if (a.size() == 1) {
            a.pop_back();

            return rez;
        }

        a[0] = a.back();
        pos[a[0].second] = 0;
        a.pop_back();
        heapify_down(0);

        return rez;
    }
};

int main() {
    int n, m;
    fin >> n >> m;

    vector<vector<pair<int, int>>> adj(n + 1); // {vecin, cost}
    for (int i = 0; i < m; i++) {
        int a, b, c;
        fin >> a >> b >> c;
        adj[a].push_back({b, c});
    }

    vector<int> dist(n + 1, INT_MAX);
    dist[1] = 0;

    IndexedHeap h;
    h.init(n);
    h.push(1, 0);

    while (!h.empty()) {
        auto [d, u] = h.extract_min();

        for (auto [v, w]: adj[u]) {
            int nd = d + w;
            if (nd < dist[v]) {
                dist[v] = nd;
                if (h.contains(v))
                    h.decrease_key(v, nd);
                else
                    h.push(v, nd);
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        fout << (dist[i] == INT_MAX ? 0 : dist[i]);
        if (i < n) fout << " ";
    }
}