#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();
    }

    inline 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> 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();
}