#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>


using namespace std;

const int NMAX = 50001;
const int CMAX = 1000000;

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

auto cmp = [](const pair<int, int>& p1, const pair<int, int>& p2)
{
    return p1.second > p2.second;
};

class graf{
private:
    int nrNoduri, nrMuchii;
    vector<pair<int, int>> listaAdsiCosturi[NMAX];
    void Dijkstra(bitset<NMAX> &viz, vector<int> &distante, priority_queue<pair<int, int>, vector<pair<int,int>>, decltype(cmp)> &minHeap);
public:
    graf(int nrNoduri, int nrMuchii) : nrNoduri(nrNoduri), nrMuchii(nrMuchii) {};
    void adaugaInListaAd(const int &nod1, const int &nod2, const int &cost);
    void afisareDijkstra();
};

void graf::adaugaInListaAd(const int &nod1, const int &nod2, const int &cost) {
    listaAdsiCosturi[nod1].push_back({nod2, cost});
}

void graf::afisareDijkstra() {
//    vector<int> tata; //reconstruire drum
//    tata.resize(nrNoduri + 1, 0);
    bitset<NMAX> viz;
    vector<int> dist;
    dist.resize(nrNoduri + 1, CMAX);
    priority_queue<pair<int, int>, vector<pair<int,int>>, decltype(cmp)> minHeap(cmp);  // primul element e nodul apoi distanta
    dist[1] = 0;
    minHeap.push({1, 0});
    Dijkstra(viz, dist, minHeap);

    for(int i = 2; i <= nrNoduri; i++){
        if(viz[i]){
            fout << dist[i] << " ";
        } else { fout << 0 << " "; }
    }
}

void graf::Dijkstra(bitset<NMAX> &viz, vector<int> &distante, priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> &minHeap) {
    while (!minHeap.empty()){
        auto top = minHeap.top();  // (nod, distanta minima)
        minHeap.pop();
        viz[top.first] = true;
        int nodCrt = top.first;
        int distCrt = top.second;
        int nrVecini = listaAdsiCosturi[nodCrt].size();
        for (int i = 0; i < nrVecini; i++){
            int vecinCrt = listaAdsiCosturi[nodCrt][i].first;
            int costCrt = listaAdsiCosturi[nodCrt][i].second;
            if (!viz[vecinCrt] and (distCrt + costCrt < distante[vecinCrt])){
                distante[vecinCrt] = distCrt + costCrt;
                minHeap.push({vecinCrt, distante[vecinCrt]});
            }
        }
    }
}

int main() {
    int noduri, muchii;
    fin>> noduri >> muchii;
    graf G(noduri, muchii);
    for(int i = 0; i < muchii; i++){
        int n1, n2, cost;
        fin >> n1 >> n2 >> cost;
        G.adaugaInListaAd(n1, n2, cost);
    }
    G.afisareDijkstra();

    return 0;
}