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

using namespace std;

template <typename T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;

using Graph = vector<vector<pair<int, int>>>;

constexpr int kInf = (1 << 30);

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

    MinHeap<pair<int, int>> heap;
    heap.push({0, start});

    while (!heap.empty()) {
        int curr_dist, node;
        tie(curr_dist, node) = heap.top();
        heap.pop();

        if (curr_dist > dist[node]) {
            continue;
        }

        for (const auto &edge : g[node]) {
            auto new_dist = curr_dist + edge.second;
            auto new_node = edge.first;

            if (new_dist < dist[new_node]) {
                dist[new_node] = new_dist;
                heap.push({new_dist, new_node});
            }
        }
    }

    vector<int> res;
    for (int i = 0; i < (int)g.size(); i += 1) {
        if (i != start) {
            res.push_back(dist[i]);
        }
    }
    return res;
}

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

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

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

    auto dist = Distances(graph, 0);
    for (const auto &d : dist) {
        fout << (d < kInf ? d : 0) << " ";
    }
    fout << "\n";

    return 0;
}