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

using namespace std;

struct nod {
    int vecini[50001];
    uint16_t cost[50001];

    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;

        noduri[nodA].vecini[noduri[nodA].nrVecini] = nodB;
        noduri[nodA].cost[noduri[nodA].nrVecini] = costArc;
        noduri[nodA].nrVecini++;
    }
    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].nrVecini; i++) {
            int vecin = noduri[nodCurent].vecini[i];
            int costVecin = noduri[nodCurent].cost[i];

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

            coada.push(vecin);
        }

        coada.pop();
    }

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

    delete noduri;

    out.close();
    return 0;
}