#include <algorithm>
#include <fstream>
#include <functional>
#include <iterator>
#include <limits>
#include <utility>
#include <vector>
#include <queue>

using edge_t = std::pair<int, int>;
using min_heap_t = std::priority_queue<edge_t, std::vector<edge_t>, std::greater<edge_t>>;
using adjancency_list_t = std::vector<std::vector<edge_t>>;

adjancency_list_t read(std::istream &in);
std::vector<int> compute_shortest_distances(const int source, const adjancency_list_t &graph);

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

    auto graph = read(fin);
    auto distances = compute_shortest_distances(0, graph);

    std::copy(distances.begin() + 1, distances.end(), std::ostream_iterator<int>(fout, " "));
    fout << std::endl;

    return 0;
}

std::vector<int> compute_shortest_distances(const int source, const adjancency_list_t &graph)
{
    std::vector<int> distances(graph.size(), std::numeric_limits<int>::max());
    min_heap_t heap;

    distances[source] = 0;
    heap.push(std::make_pair(0, source));

    int u, v, min, dist;
    while (!heap.empty())
    {
        std::tie(min, v) = heap.top();
        heap.pop();

        if (distances[v] == min)
            for (const auto edge : graph[v])
            {
                dist = edge.first;
                u = edge.second;

                if (distances[v] + dist < distances[u])
                {
                    distances[u] = distances[v] + dist;
                    heap.push(std::make_pair(distances[u], u));
                }
            }
    }

    std::transform(distances.begin(), distances.end(), distances.begin(),
                   [](const int &x) { return (x != std::numeric_limits<int>::max()) ? x : 0; });

    return distances;
}

adjancency_list_t read(std::istream &in)
{
    int V, E;
    in >> V >> E;

    adjancency_list_t graph(V);

    int u, v, d;
    for (int i = 0; i < E; ++i)
    {
        in >> u >> v >> d;
        graph[u - 1].push_back(std::make_pair(d, v - 1));
    }

    return graph;
}