// http://www.infoarena.ro/problema/apm
// Rezolvat prin Prim

//-1 000 <= C <= 1 000
//Infinit = 1001
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>
using namespace std;

class cmp
{
public:
    bool operator()(pair <int, int> st, pair <int, int> dr){
        return st.second > dr.second;
    }
};

class graf
{
private:
    /*
    N = nr. noduri
    M = nr. muchii
    p = vector costuri
    V = lista de adiacenta V[muchie_1] = makepair(muchie_2, cost)
    V2 = arborele de cost minim
    Q = vectorul de chei
    vis = lista de noduri vizitate
    */
    int N, M;
    vector <int> cheie;
    vector <list <pair <int, int> > > V;
    vector <int> vis;
public:
    graf(){
        ifstream f("dijkstra.in");
        //Citim numarul de noduri si muchii
        f>>N>>M;
        //Initializam dimensiunile vectorilor
        //V.resize(N+1);
        cheie.resize(N+1); //Costul pana in nodul respectiv, infinit = mai mare ca val maxima = nevizitat
        vis.resize(N+1);
        V.resize(N+1);
        int i, aux1, aux2, aux3;
        //Citim matricea si inseram nodurile in lista de adiacenta
        for(i=0; i<M; i++){
            f>>aux1>>aux2>>aux3;
            V[aux1].push_back(make_pair(aux2, aux3) );
            V[aux2].push_back(make_pair(aux1, aux3) );
        }
        f.close();
    }

    void dijkistra(){
        priority_queue <pair <int, int>, vector <pair <int, int> >, cmp > Q; //first = nod, second = distanta pana in nodul respectiv
        vector <int> vis; //0 = nevizitats
        pair <int, int> u;
        int aux, i, ramas;
        list <pair <int, int> >::iterator parc;
        cheie[1]=0;
        for(i=2; i<=N; i++)
            cheie[i]=-1; //-1 = nevizitat, pe motiv ca drum minim poate fi mai mare ca arc maxim
        vis.resize(N+1);
        Q.push(make_pair(1, 0));
        ramas = N; //Numarul de noduri ne-vizitate, modificam dupa
        while(!Q.empty() && ramas>0){
            //Cat timp exista noduri in pq
            u=Q.top();
            while(vis[u.first]==1){
                //Daca deja a fost vizitat, ii dam pop si trecem la urmatorul
                Q.pop();
                u=Q.top();
            }
            //Dupa ce ajungem la unul nevizitat, ii dam pop din Q
            Q.pop();
            parc = V[u.first].begin();
            vis[u.first]=1;
            //Parcurgem toate nodurile si modificam costurile dupa cum este necesar
            while(parc != V[u.first].end()){
                cout<<"cheie de "<<u.first<<" == "<<cheie[u.first]<<endl;
                aux=(*parc).second+cheie[u.first]; //aux = cost muchie + cost pana in nodul respectiv
                //Si daca cheia nodului este neinitializata sau mai mare, o modificam
                if(aux < cheie[(*parc).first] || cheie[(*parc).first] == -1){
                    cheie[(*parc).first] = aux;
                    Q.push(make_pair((*parc).first, aux));
                }
                parc++;
            }
            ramas--;
        }

        //Am incheiat, afisam rezultatul
        ofstream g("dijkstra.out");
        for(i=2; i<=N; i++)
            g<<cheie[i]<<" ";
        g.close();

    }
};

int main()
{
    graf V;
    V.dijkistra();
    return 0;
}