#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]] = 1;
        for (int i=0; i<noduri[cauta[t]].size(); ++i) {
            if (iiGata[noduri[cauta[t]][i].destinatie]) continue;
            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;
            }
        }

        int lowest = max;
        int lowestID;
        for (int i=2; i<=n; ++i) {
            //std::cout << i << "(" << distanta[i] << ")(" << iiGata[i] << ") ";
            if (!iiGata[i] && distanta[i] < lowest) {
                lowest = distanta[i];
                lowestID = i;
            }
        } //std::cout << "\nlowest=" << lowest << " | " << lowestID << "\n";
        if (lowest != max) {
            cauta.push_back(lowestID);
        }
        ++t;
    }

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