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

using namespace std;

struct vecin {
    int nodVecin;
    uint16_t cost;
};

struct nod {
    list<vecin> vecini;
};

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 = new int[nrNoduri + 1]();
    bool *verificat = new bool[nrNoduri + 1]();

    for(int i = 1; i <= nrNoduri; i++) {
        int nodCurent = i;

        for(list<vecin>::iterator it=noduri[nodCurent].vecini.begin(); it != noduri[nodCurent].vecini.end(); ++it){
            int nodVecin = it->nodVecin;
            uint16_t costVecin = it->cost;

            if((drumMinim[nodVecin] == 0 || drumMinim[nodCurent] + costVecin < drumMinim[nodVecin]) && !verificat[i])
                drumMinim[nodVecin] = drumMinim[nodCurent] + costVecin;
        }

        verificat[i] = true;
    }

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

    delete noduri;
    delete drumMinim;
    delete verificat;

    out.close();
    return 0;
}