#include <fstream>
#include <vector>
#include <list>
#include <queue>
#include <limits>
#include <algorithm>


using intPair = std::pair<int, int>;
using listOfPairs = std::list<intPair>;
using vecOfLists = std::vector<listOfPairs>;
using vecOfPairs = std::vector<intPair>;
using pq = std::priority_queue<intPair, vecOfPairs, std::greater<intPair>>;


std::vector<int> computeDists(const vecOfLists &adj_list, int s_node)
{
    std::vector<int> dists(adj_list.size(), std::numeric_limits<int>::max());
    pq Q;

    dists[s_node] = 0;
    Q.emplace(dists[s_node], s_node);

    while (!Q.empty()) {
        auto curr_entry = Q.top();
        Q.pop();

        if (curr_entry.first == dists[curr_entry.second]) {
            for (auto &i : adj_list[curr_entry.second]) {
                auto cost = i.second;
                auto vertex = i.first;

                if (curr_entry.first + cost < dists[vertex]) {
                    dists[vertex] = curr_entry.first + cost;
                    Q.emplace(dists[vertex], vertex);
                }
            }
        }
    }

    return dists;
}

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

    int N, M;
    fin >> N >> M;

    vecOfLists adj_list(N);
    for (int i = 0; i < M; ++i) {
        int x, y, cost;
        fin >> x >> y >> cost;
        --x, --y;

        adj_list[x].emplace_back(y, cost);
    }

    auto lengths = computeDists(adj_list, 0);
    std::for_each(
            lengths.cbegin() + 1,
            lengths.cend(),
            [&fout](const decltype(lengths)::value_type& elem) {
                fout << (elem == std::numeric_limits<int>::max() ? 0 : elem)
                     << " ";
    });

    return 0;
}