#include <fstream>
#include <queue>
#include <vector>

using namespace std;

struct Node
{
    vector<pair<int, int>> edges;
};

using Graph = vector<Node>;

struct DijkstraInfo
{
    int node;
    int cost;
};

struct DijkstraCmp
{
    bool operator()(const DijkstraInfo &a, const DijkstraInfo &b)
    {
        return a.cost > b.cost;
    }
};

using Heap = priority_queue<DijkstraInfo, vector<DijkstraInfo>, DijkstraCmp>;

vector<int> Dijkstra(const Graph &g, int start)
{
    vector<int> costs(g.size(), (1 << 30));
    costs[start] = 0;

    Heap heap;
    heap.push({.node = start, .cost = 0});

    while (!heap.empty()) {
        auto node = heap.top().node;
        auto cost = heap.top().cost;
        heap.pop();

        if (cost > costs[node]) {
            continue;
        }

        for (const auto &e : g[node].edges) {
            auto next_node = e.first;
            auto next_cost = cost + e.second;
            if (next_cost < costs[next_node]) {
                costs[next_node] = next_cost;
                heap.push({.node = next_node, .cost = next_cost});
            }
        }
    }
    return costs;
}

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

    int nodes, edges;
    fin >> nodes >> edges;

    Graph graph(nodes);
    for (auto i = 0; i < edges; i += 1) {
        int a, b, cost;
        fin >> a >> b >> cost;
        graph[a - 1].edges.push_back({b - 1, cost});
    }

    auto costs = Dijkstra(graph, 0);
    for (auto i = 1; i < nodes; i += 1) {
        fout << costs[i] << " ";
    }
    fout << "\n";

    return 0;
}