#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<algorithm>
#include<climits>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

class graf{
protected:
    int NrMuchii, NrNoduri;
    bool eOrientat;
    vector<vector<int>> adiacenta;

public:
    graf(int NrNod = 0, int NrMuc = 0, bool orientat = false, vector<vector<int>> adiacenta = {}){
        this->NrNoduri = NrNod;
        this->NrMuchii = NrMuc;
        this->eOrientat = orientat;
    }
    ~graf(){
        this->NrNoduri = 0;
        this->NrMuchii = 0;
    }
    void setNrNoduri(int&);
    void setNrMuchii(int&);
    void setMuchii(int, int);
    int getNrNoduri();
    int getNrMuchii();
    void citireMuchii();
    void BFS(int, bool[], int[]);
    void DFS(int, bool[]);
    int NrComponenteConexe(bool[]);
    int gaseste(int, vector<int> &);
    void uneste(int, int, vector<int> &);
    vector<int> disjoint(vector<pair<int, pair<int, int>>>);
};

class grafCuCost : public graf
{
private:
    vector<vector<int>> costMuchii;
    vector<vector<pair<pair<int, int>, int>>> costuriVecini;

public:
    grafCuCost(int NrNoduri = 0, int NrMuchii = 0, bool orientat = false, vector<vector<int>> adiacenta = {}, vector<vector<int>> costMuchii = {}) : graf(NrNoduri, NrMuchii, orientat, adiacenta)
    {
        this->costMuchii = costMuchii;
    }
    void setMuchiiCost(int, int, int);
    vector<vector<int>> apm(vector<int> &, int &);
    vector<int> Bellman_Ford(int);
    vector<int> Dijkstra(int);
};

void grafCuCost::setMuchiiCost(int n1, int n2, int cost){
    pair<pair<int, int>, int> muchieCost;
    costuriVecini.resize(this->NrNoduri + 1);
    muchieCost = make_pair(make_pair(n1, n2), cost);
    costuriVecini[n1].push_back(muchieCost);
    if(this->eOrientat == false){
        costuriVecini[n2].push_back(muchieCost);
    }
}

void graf::setNrNoduri(int &n){
    NrNoduri = n;
}

void graf::setNrMuchii(int &m){
    NrMuchii = m;
}

void graf::setMuchii(int nod1, int nod2){
    adiacenta[nod1].push_back(nod2);
}

int graf::getNrNoduri(){
    return NrNoduri;
}

int graf::getNrMuchii(){
    return NrMuchii;
}

void graf::citireMuchii(){
    int n1, n2;
    adiacenta.resize(NrNoduri + 1);
    for(int i = 0; i < NrMuchii; i++){
        in>>n1>>n2;
        setMuchii(n1, n2);
        if(!eOrientat){
            setMuchii(n2, n1);
        }
    }
}

void graf::BFS(int NodSursa, bool vizitat[], int distanta[]){
    queue<int> coada;
    coada.push(NodSursa);
    vizitat[NodSursa] = true;
    while(!coada.empty()){
        for(int nod : adiacenta[coada.front()]){
            if(!vizitat[nod]){
                vizitat[nod] = true;
                coada.push(nod);
                distanta[nod] = distanta[coada.front()] + 1;
            }
        }
        coada.pop();
    }
    for(int nod = 1; nod <= NrNoduri; nod++){
        if((NodSursa != nod) && (distanta[nod] == 0)){
            out<<"-1 ";
        }
        else{
            out<<distanta[nod]<<" ";
        }
    }
}

void graf::DFS(int Nod, bool vizitat[]){
    vizitat[Nod] = true;
    for(int vecin : adiacenta[Nod]){
        if(!vizitat[vecin]){
            DFS(vecin, vizitat);
        }
    }
}

int graf::NrComponenteConexe(bool vizitat[]){
    int NrCompCon = 0;
    for(int Nod = 1; Nod <= NrNoduri; Nod++){
        if(!vizitat[Nod]){
            NrCompCon++;
            DFS(Nod, vizitat);
        }
    }
    return NrCompCon;
}

int graf::gaseste(int nod, vector<int> &radacina){
    if(radacina[nod] != nod){
        radacina[nod] = gaseste(radacina[nod], radacina);
    }
    return radacina[nod];
}

void graf::uneste(int x, int y, vector<int> &radacina){
    int rad1, rad2;
    rad1 = gaseste(x, radacina);
    rad2 = gaseste(y, radacina);
    radacina[rad1] = rad2;
}

vector<int> graf::disjoint(vector<pair<int,pair<int, int>>> operatii){
    vector<int> radacina(NrNoduri + 1);
    vector<int> rez;
    for(int i = 0; i < NrNoduri; i++){
        radacina[i] = i;
    }
    for(int i = 0; i < operatii.size(); i++){
        int cod = operatii[i].first;
        int x = operatii[i].second.first;
        int y = operatii[i].second.second;
        if(cod == 1){
            uneste(x, y, radacina);
        }
        else{
            if(cod == 2){
                if(gaseste(x, radacina) == gaseste(y, radacina)){
                    rez.push_back(1);
                }
                else{
                    rez.push_back(0);
                }
            }
        }
    }
    return rez;
}

bool compara(vector<int> v1, vector<int> v2){
    return v1[2] < v2[2];
}

vector<vector<int>> grafCuCost::apm(vector<int> &parinte, int &costTotal){
    vector<vector<int>> rez;
    int nod1, nod2, p1, p2, i;
    i = 0;
    sort(costMuchii.begin(), costMuchii.end(), compara);
    while(rez.size() < NrNoduri - 1){
        nod1 = costMuchii[i][0];
        nod2 = costMuchii[i][1];
        p1 = nod1;
        p2 = nod2;
        p1 = gaseste(nod1, parinte);
        p2 = gaseste(nod2, parinte);
        if(p1 != p2){
            if(p1 < p2){
                parinte[p1] = parinte[p2];
            }
            else{
                parinte[p2] = parinte[p1];
            }
            rez.push_back({nod1, nod2});
            costTotal += costMuchii[i][2];
        }
        i++;
    }
    return rez;
}

vector<int> grafCuCost::Bellman_Ford(int nod){
    vector<int> costMin(NrNoduri + 1, INT_MAX);
    vector<int> vizitat(NrNoduri + 1, 0);
    vector<int> inCoada(NrNoduri + 1, 0);
    queue<int> coada;
    costMin[nod] = 0;
    coada.push(nod);
    inCoada[nod] = 1;
    while(!coada.empty()){
        int nodCurent = coada.front();
        vizitat[nodCurent]++;
        if(vizitat[nodCurent] >= NrNoduri){
            return {-1};
        }
        coada.pop();
        inCoada[nodCurent] = 0;
        for(auto i : costuriVecini[nodCurent]){
            int vecin = i.first.second;
            int cost = i.second;
            if(costMin[nodCurent] + cost < costMin[vecin]){
                costMin[vecin] = costMin[nodCurent] + cost;
                if(!inCoada[vecin]){
                    coada.push(vecin);
                    inCoada[vecin] = 1;
                }
            }
        }
    }
    return costMin;
}

vector<int> grafCuCost::Dijkstra(int nod){
    vector<int> costMin(NrNoduri + 1, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> coadaPri;
    costMin[nod] = 0;
    coadaPri.push({nod, 0});
    while(!coadaPri.empty()){
        int nodCurent = coadaPri.top().first;
        coadaPri.pop();
        for(auto i : costuriVecini[nodCurent]){
            int vecin = i.first.second;
            int cost = i.second;
            if(costMin[nodCurent] + cost < costMin[vecin]){
                costMin[vecin] = costMin[nodCurent] + cost;
                coadaPri.push({vecin, costMin[vecin]});
            }
        }
    }
    for(int i = 2; i <= NrNoduri; i++){
        if(costMin[i] == INT_MAX){
            costMin[i] = 0;
        }
    }
    return costMin;
}

void InfoArena_BFS(){
    int N, M, Sursa;
    in>>N>>M>>Sursa;
    graf G(N, M, true);
    G.citireMuchii();
    bool vizitat[N + 1] = {false};
    int distanta[N + 1] = {0};
    G.BFS(Sursa, vizitat, distanta);
}

void InfoArena_DFS(){
    int N, M;
    in>>N>>M;
    graf G(N, M, false);
    G.citireMuchii();
    bool vizitat[N + 1] = {false};
    out<<G.NrComponenteConexe(vizitat);
}

void InfoArena_disjoint(){
    int N, M, cod, x, y;
    in>>N>>M;
    graf G(N, 0, false);
    vector<pair<int, pair<int, int>>> operatii;
    for(int i = 0; i < M; i++){
        in>>cod>>x>>y;
        operatii.push_back(make_pair(cod, make_pair(x, y)));
    }
    vector<int> rez = G.disjoint(operatii);
    for(int i = 0; i < rez.size(); i++){
        if(rez[i]){
            out<<"DA"<<"\n";
        }
        else{
            out<<"NU"<<"\n";
        }
    }
}

void InfoArena_apm(){
    int N, M, X, Y, C;
    in>>N>>M;
    vector<vector<int>> adiacenta(N + 1, {0});
    vector<vector<int>> costMuchii;
    for(int i = 0; i < M; i++){
        in>>X>>Y>>C;
        costMuchii.push_back({X, Y, C});
    }
    grafCuCost G(N, M, false, adiacenta, costMuchii);
    vector<int> parinte(N + 1);
    for(int i = 1; i < parinte.size(); i++){
        parinte[i] = i;
    }
    int costTotal = 0;
    vector<vector<int>> rez = G.apm(parinte, costTotal);
    out<<costTotal<<"\n"<<rez.size()<<"\n";
    for(int i = 0; i < rez.size(); i++){
        out<<rez[i][0]<<" "<<rez[i][1]<<"\n";
    }

}

void InfoArena_BellmanFord(){
    int N, M, x, y, c;
    in>>N>>M;
    grafCuCost G(N, M, true);
    for(int i = 0; i < M; i++){
        in>>x>>y>>c;
        G.setMuchiiCost(x, y, c);
    }

    vector<int> costMinim = G.Bellman_Ford(1);
    if(costMinim[0] == -1){
        out<<"Ciclu negativ!";
    }
    else{
        for(int i = 2; i < costMinim.size(); i++){
            out<<costMinim[i]<<" ";
        }
    }
}

void InfoArena_Dijkstra(){
    int N, M, A, B, C;
    in>>N>>M;
    grafCuCost G(N, M, true);
    for(int i = 0; i < M; i++){
        in>>A>>B>>C;
        G.setMuchiiCost(A, B, C);
    }
    vector<int> costMinim = G.Dijkstra(1);
    for(int i = 2; i < costMinim.size(); i++){
        out<<costMinim[i]<<" ";
    }
}

int main()
{
    //InfoArena_BFS();
    //InfoArena_DFS();
    //InfoArena_disjoint();
    //InfoArena_apm();
    //InfoArena_BellmanFord();
    InfoArena_Dijkstra();
    return 0;
}