#include <fstream>
#include <vector>
#define DIM 50010
#define INF 1000000000

using namespace std;
vector<pair<int, int> > L[DIM];
int v[DIM], D[DIM];
int n, m, i, nod, vecin, cost, x, y, c, minim;
int main () {
    ifstream fin ("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin>>n>>m;

    for (i=1;i<=m;i++){
        fin>>x>>y>>c;
        L[x].push_back( make_pair(y, c) );
        L[y].push_back( make_pair(x, c) ); /// adaug asta, adica am graf neorientat
    }

    D[1] = 0;
    for (i=2;i<=n;i++)
        D[i] = INF;

    for (;;) {
        minim = INF;
        for (i=1;i<=n;i++)
            if (v[i] == 0 && D[i] < minim) {
                minim = D[i];
                nod = i;
            }
        if (minim == INF)
            break;

        v[nod] = 1;
        for (i=0;i<L[nod].size();i++) {
            vecin = L[nod][i].first;
            cost = L[nod][i].second;

            if (D[vecin] > /**D[nod] +**/ cost) {
                D[vecin] = /**D[nod] +**/ cost;
                t[vecin] = nod; /**adaug asta**/
            }
        }
    }

    /// afisez asa
    for (i=1;i<=n;i++)
        if (t[i] != 0)
            muchie(i, t[i]);


/**
    for (i=2;i<=n;i++)
        if (D[i] == INF)
            fout<<"0 ";
        else
            fout<<D[i]<<" ";
**/
    return 0;
}

/**

nodurile insemnate cu 1 formeaza un subarbore in jurul
nodului de pornire
acum D[i] reprezinta distanta minima de la un nod inca neales
la un nod din subarborele format de cele alese

Daca la Kruskal construiesc APM alegand muchie cu muchie, Greedy
la PRIM construiesc AMP adaugand nod cu nod Greedy


**/