#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> 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);
    typedef std::pair<int, int> P;
    std::vector<std::vector<P>> adj_list;

    std::ifstream fin("dijkstra.in");
    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();

    int k = 1;

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


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