#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

struct vecin {
    int nodVecin;
    uint16_t cost;
};

struct nod {
    vector<vecin> vecini;

    int nrVecini;
};

int main() {
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");

    if(!in.good() || !out.good())
        return 1;

    int nrNoduri, nrArce;
    in >> nrNoduri >> nrArce;

    nod* noduri = new nod[nrNoduri + 1];

    for(int i = 0; i < nrArce; i++) {
        int nodA, nodB;
        uint16_t costArc;

        in >> nodA >> nodB >> costArc;

        vecin nodVecin;
        nodVecin.nodVecin = nodB;
        nodVecin.cost = costArc;

        noduri[nodA].vecini.push_back(nodVecin);
    }
    in.close();

    int drumMinim[50001] = {};

    queue<int> coada;
    coada.push(1);

    while(!coada.empty()) {
        int nodCurent = coada.front();

        for(int i = 0; i < noduri[nodCurent].vecini.size(); i++) {
            int nodVecin = noduri[nodCurent].vecini[i].nodVecin;
            uint16_t costVecin = noduri[nodCurent].vecini[i].cost;

            if(drumMinim[nodVecin] == 0 || drumMinim[nodCurent] + costVecin < drumMinim[nodVecin])
                drumMinim[nodVecin] = drumMinim[nodCurent] + costVecin;

            coada.push(nodVecin);
        }

        coada.pop();
    }

    for(int i = 2; i <= nrNoduri; i++)
        out << drumMinim[i] << " ";

    delete noduri;

    out.close();
    return 0;
}