#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
using VI = vector<int>;
using VPI = vector<vector<pair<int, int>>>;

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

const int Inf = 1 << (sizeof(int) * 8 - 2);

struct CmpByVal {
    VI const &D;
    VI P;
    CmpByVal(VI const &D) : D{D}, P(D.size(), -1) {}
    bool operator () (int a, int b) { // not const
        bool need_swap = D[a] > D[b];
        if(need_swap) {
            swap(P[a], P[b]);
            //cout << "(swapped " << a << ' ' << b << ") ";
        }
        return need_swap;
    }
};

struct Heap {
    VI container;
    VI const &D;
    CmpByVal cmp;
    Heap(VI const &D) : D{D}, cmp(D) {}
    void push(int node) {
        cmp.P[node] = container.size();
        container.push_back(node);
        push_heap(container.begin(), container.end(), cmp);
    }
    void pop() {
        swap(cmp.P[container.front()], cmp.P[container.back()]);
        pop_heap(container.begin(), container.end(), cmp);
        container.pop_back();
        // cmp.P.pop_back();
    }
    void update(int node) {
        push_heap(container.begin(), container.begin() + (1 + cmp.P[node]), cmp);
    }
    inline bool empty() {
        return container.empty();
    }
    inline int front() {
        return container.front();
    }
};

void Dijkstra(int node, VI &D, VPI &G) {
    Heap H(D);

    D[node] = 0;
    H.push(node);
    // push_heap(H.begin(), H.end(), cmp);

    while (!H.empty()) {
        /*for(auto v : H.container) cout << v << ' ';
        cout << "- ";
        for(auto v : H.cmp.P) cout << v << ' ';
        cout << "\n";*/

        int x = H.front();
        H.pop();

        for(auto [y, w] : G[x]) {
            //cout << "nod " << x << ' ' << y << '\n';
            if(D[y] > D[x] + w) {
                bool inHeap = D[y] != Inf;
                D[y] = D[x] + w;
                if(inHeap) {
                    H.update(y);
                } else {
                    H.push(y);
                }
            }
        }
    }
}

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

    VPI G(n);
    VI D(n, Inf); /// D - weights

    int x, y, w;
    for (int i=0; i<m; ++i) {
        fin >> x >> y >> w;
        x -= 1; y -= 1;
        G[x].emplace_back(y, w);
        G[y].emplace_back(x, w);
    }

    Dijkstra(0, D, G);

    for(auto it = D.begin()+1; it < D.end(); ++it) fout << (*it == Inf ? 0 : *it) << ' ';

    return 0;
}