#include <iostream>
#include <fstream>
#include <vector>

const int max = 1 << 30;

struct muchie {
    int destinatie;
    int valoare;
};
std::vector<muchie> noduri[50001];
int distanta[50001];
bool iiGata[50001];

int main() {
    std::ifstream f("dijkstra.in");
    int n, m;
    f >> n >> m;

    int x, y, c;
    for (int i=0; i<m; ++i) {
        f >> x >> y >> c;
        muchie m; m.destinatie=y; m.valoare=c;
        noduri[x].push_back(m);
    }

    // for (int i=1; i<=n; ++i) {
    //     std::cout << i << "\n\t";
    //     for (int j=0; j<noduri[i].size(); ++j) {
    //         std::cout << noduri[i][j].destinatie << " ";
    //     }
    //     std::cout << "\n";
    // }

    for (int i=2; i<=n; ++i) {
        distanta[i] = max;
    }

    std::vector<int> cauta;
    cauta.push_back(1);
    int t = 0;
    while (t < cauta.size()) {
        //std::cout << cauta[t] << "\n";
        iiGata[cauta[t]] = 0;
        for (int i=0; i<noduri[cauta[t]].size(); ++i) {
            int newDistanta = distanta[cauta[t]] + noduri[cauta[t]][i].valoare;
            //std::cout << "\t" << newDistanta << " " << (newDistanta < distanta[noduri[cauta[t]][i].destinatie]) << " " << noduri[cauta[t]][i].destinatie << "\n";
            if (newDistanta < distanta[noduri[cauta[t]][i].destinatie]) {
                distanta[noduri[cauta[t]][i].destinatie] = newDistanta;

                if (!iiGata[noduri[cauta[t]][i].destinatie]) {
                    iiGata[noduri[cauta[t]][i].destinatie] = 1;
                    cauta.push_back(noduri[cauta[t]][i].destinatie);
                }
            }
        }
        ++t;
    }

    std::ofstream g("dijkstra.out");
    for (int i=2; i<=n; ++i) {
        g << distanta[i] << " ";
    }
    return 0;
}