#include <fstream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

class Graf {
private:
    int nrNoduri; // Numărul de noduri
    vector<vector<pair<int, int>>> adiacenta; // Lista de adiacență {vecin, cost}

public:
    Graf(int nrNoduri);

    void adaugaMuchie(int sursa, int destinatie, int cost);

    void citire(int nrMuchii);

    void rezolvaDijkstra(); // Algoritmul Dijkstra
};

Graf::Graf(int nrNoduri) {
    this->nrNoduri = nrNoduri;
    adiacenta.resize(nrNoduri + 1); // Alocare memorie pentru lista de adiacență
}

void Graf::adaugaMuchie(int sursa, int destinatie, int cost) {
    adiacenta[sursa].emplace_back(destinatie, cost); // Adăugăm muchia cu costul în lista sursei
}

void Graf::citire(int nrMuchii) {
    int sursa, destinatie, cost;
    for (int i = 0; i < nrMuchii; ++i) {
        fin >> sursa >> destinatie >> cost;
        adaugaMuchie(sursa, destinatie, cost); // Citim și adăugăm muchia
    }
}

void Graf::rezolvaDijkstra() {
    const int inf = INT_MAX; // Reprezintă distanța infinită
    vector<int> distanta(nrNoduri + 1, inf); // Inițializăm toate distanțele cu infinit
    vector<bool> vizitat(nrNoduri + 1, false); // Marcam nodurile nevizitate
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> minHeap; // Coada de priorități {distanță, nod}

    distanta[1] = 0; // Distanța până la nodul de start (1) este 0
    minHeap.emplace(0, 1); // Adăugăm nodul de start în coadă

    while (!minHeap.empty()) {
        int nod = minHeap.top().second; // Extrag nodul cu cea mai mică distanță
        minHeap.pop();

        if (vizitat[nod]) continue; // Dacă nodul a fost deja vizitat, trecem peste
        vizitat[nod] = true; // Marcam nodul ca vizitat

        for (const auto& vecin : adiacenta[nod]) {
            int nodVecin = vecin.first; // Nodul vecin
            int costMuchie = vecin.second; // Costul muchiei către vecin

            // Actualizăm distanța dacă găsim un drum mai scurt
            if (distanta[nod] + costMuchie < distanta[nodVecin]) {
                distanta[nodVecin] = distanta[nod] + costMuchie;
                minHeap.emplace(distanta[nodVecin], nodVecin); // Adăugăm vecinul cu distanța actualizată în coadă
            }
        }
    }

    // Afișăm distanțele finale către toate nodurile
    for (int i = 2; i <= nrNoduri; ++i) {
        if (distanta[i] == inf)
            fout << 0 << " "; // Dacă distanța este infinit, afișăm 0
        else
            fout << distanta[i] << " ";
    }
}

int main() {
    int nrNoduri, nrMuchii;
    fin >> nrNoduri >> nrMuchii;

    Graf g(nrNoduri);
    g.citire(nrMuchii);
    g.rezolvaDijkstra();

    fin.close();
    fout.close();
    return 0;
}