#include <vector>
#include <fstream>
#include <queue>
#include <iostream>
#include <limits>
#include <map>

using namespace std;

vector<vector<pair<int,int>>> V; // V[from] = [to, dist]

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

    int N,M;
    fin>>N>>M;
    V.resize(N);
    for(int i=0;i<M;i++) {
        int from, to, dist;
        fin>>from>>to>>dist;
        from--;
        to--;
        V[from].push_back({to, dist});
    }

    vector<int> D(N, numeric_limits<int>::max());
    D[0] = 0;

    // Using lambda to compare elements.
    using entry_t = pair<int,int>; // node, dist
    auto cmp = [](auto left, auto right) { return left.first < right.first; };
    std::priority_queue<entry_t , std::vector<entry_t>, decltype(cmp)> Q(cmp);

//    map<int, int> Q; // <dist, node>
    Q.emplace(0, 0);
    while(!Q.empty()) {
        auto curr = Q.top().first;
        Q.pop();
        for(const auto& item : V[curr]) {
            auto to = item.first;
            auto dist = item.second;
            if (D[curr] + dist < D[to]) {
                D[to] = D[curr] + dist;
                Q.emplace(D[to], to);
            }
        }
    }
    for(int i=1; i<N; i++) {
        if(D[i] == numeric_limits<int>::max()) {
            D[i] = 0;
        }
        fout<<D[i]<<' ';
    }



}