#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <limits>

class Graph {
public:
    Graph(const std::string &
    filename) {
        std::ifstream fin(filename);
        int n, m;
        fin >> n >> m;
        adj_list.resize(n + 1, std::vector<P>());

        int f, g, h;
        for (int i = 0; i < m; i++) {
            fin >> f >> g >> h;
            adj_list[f].push_back(P{g, h});
        }

        fin.close();
    }

    std::vector<int> *djikstra(int k) {
        std::vector<int> *dist = new std::vector<int>(adj_list.size(), std::numeric_limits<int>::max());
        std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
        pq.push(P{0, k});
        (*dist)[k] = 0;

        P top;
        while (!pq.empty()) {
            top = pq.top();
            pq.pop();

            if (top.first == (*dist)[top.second]) {
                for (P e:adj_list[top.second]) {
                    if ((*dist)[e.first] > (*dist)[top.second] + e.second) {
                        (*dist)[e.first] = (*dist)[top.second] + e.second;
                        pq.push(P{(*dist)[e.first], e.first});
                    }
                }
            }
        }
        return dist;
    }

private:
    typedef std::pair<int, int> P;
    std::vector<std::vector<P>> adj_list;

};

int main() {
    Graph graph("dijkstra.in");
    std::vector<int> *a = graph.djikstra(1);

    std::ofstream fout("dijkstra.out");
    for (int i = 2; i < a->size(); i++) fout << ((*a)[i] == std::numeric_limits<int>::max() ? 0 : (*a)[i]) << " ";
    fout.close();
}