#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
#include <assert.h>
#include <queue>
#include <functional>


using LL = long long;
using ULL = int long long;

const std::string _problemName = "dijkstra";

namespace std {
std::ifstream fin(_problemName + ".in");
std::ofstream fout(_problemName + ".out");
}

#define USE_FILES

#ifdef USE_FILES
#define cin fin
#define cout fout
#endif

struct Arc {
    int toNode;
    int distance;

    Arc(int toNode, int distance) {
        this->toNode = toNode;
        this->distance = distance;
    }

    bool operator< (const Arc& other) const {
        if (distance != other.distance) {
            return distance < other.distance;
        }
        return toNode < other.toNode;
    }
};

const int INF = 1 << 30;
using graph_t = std::vector<std::vector<Arc>>;

std::vector<int> runDijkstra(const graph_t& graph, int startNode) {
    std::vector<int> distances(graph.size(), INF);
//    std::vector<bool> done(graph.size(), true);

    distances[startNode] = 0;

    auto comparator = [&distances](int left, int right) {
        return distances[left] < distances[right];
    };

    using priority_queue_t = std::priority_queue<
            int,
            std::vector<int>,
            std::function<bool(int, int)>
    >;

    priority_queue_t currentBorder(comparator);

    currentBorder.push(startNode);

    while (!currentBorder.empty()) {
        int current = currentBorder.top(); // smallest
        currentBorder.pop();

        for (const auto& arc : graph[current]) {
            if (distances[arc.toNode] > distances[current] + arc.distance) {
                if (distances[arc.toNode] != INF) {
                    // currentBorder.erase(Arc(arc.toNode, distances[arc.toNode]));
                }

                distances[arc.toNode] = distances[current] + arc.distance;
                currentBorder.emplace(arc.toNode, distances[arc.toNode]);
            }
        }
    }

    for (auto& dist : distances) {
        if (dist == INF) {
            dist = 0;
        }
    }

    return distances;
}

int main() {

    int n, m;
    std::cin >> n >> m;

    graph_t graph(n);

    while (m--) {
        int a, b, d;
        std::cin >> a >> b >> d;
        --a, --b;
        graph[a].emplace_back(b, d);
    }

    std::vector<int> distances = runDijkstra(graph, 0);

    for (int idx = 1; idx < distances.size(); ++idx) {
        std::cout << distances[idx] << ' ';
    }
    std::cout << '\n';


    return 0;
}