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

using namespace std;

using Pair = pair<int, int>;
using Graph = vector<vector<Pair>>;
using MinHeap = priority_queue<Pair, vector<Pair>, greater<Pair>>;

constexpr auto kInf = (1 << 30);

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

    MinHeap heap;
    heap.push({costs[start], start});

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

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

        for (const auto &e : g[node]) {
            if (cost + e.second < costs[e.first]) {
                costs[e.first] = cost + e.second;
                heap.push({costs[e.first], e.first});
            }
        }
    }
    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].push_back({b - 1, cost});
    }

    auto res = FindDist(graph, 0);
    for (auto i = 1; i < nodes; i += 1) {
        fout << (res[i] < kInf ? res[i] : 0) << " ";
    }
    fout << "\n";

    return 0;
}