#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(adj_list.size(), std::numeric_limits<int>::max()/2);
        std::priority_queue<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]<<" ";
    fout.close();
}