#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#define infinit 1<<30
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
void citire(int n, int m, vector<pair<int,int> > *&Adiacenta, bool *&Vizitat, int *&Tati,int *&Costuri_actuale){
    int nod1, nod2, cost;
    Adiacenta = new vector<pair<int,int> >[n+1]();
    Vizitat = new bool[n+1]();
    Tati = new int[n+1]();
    Costuri_actuale = new int[n+1]();
    for(int i = 0 ; i < m ; i++){
        fin >> nod1 >> nod2 >> cost;
        Adiacenta[nod1].push_back(make_pair(cost,nod2));
        Adiacenta[nod2].push_back(make_pair(cost,nod1));
    }
    for(int i = 1 ; i <= n ; i++)
        Costuri_actuale[i] = infinit;
}
int main()
{
    int  n, m, *Costuri_actuale, *Tati;
    bool *Vizitat;
    priority_queue< pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;
    vector<pair<int,int> > *Adiacenta;
    fin >> n >> m;
    citire(n, m, Adiacenta, Vizitat, Tati, Costuri_actuale);
    Costuri_actuale[1] = 0;
    Vizitat[1] = 1;
    pq.push(make_pair(Costuri_actuale[1], 1));
    while(!pq.empty()){
        for(unsigned int i = 0 ; i < Adiacenta[pq.top().second].size() ; i++){
            if(Adiacenta[pq.top().second][i].first + Costuri_actuale[pq.top().second] < Costuri_actuale[Adiacenta[pq.top().second][i].second] && Vizitat[Adiacenta[pq.top().second][i].second] == 0){
                Costuri_actuale[Adiacenta[pq.top().second][i].second] = Adiacenta[pq.top().second][i].first + Costuri_actuale[pq.top().second];
                Tati[Adiacenta[pq.top().second][i].second] = pq.top().second;
                pq.push(make_pair(Costuri_actuale[Adiacenta[pq.top().second][i].second], Adiacenta[pq.top().second][i].second));
                cout << "Am adaugat nodul " << Adiacenta[pq.top().second][i].second << " cu costul" << Costuri_actuale[Adiacenta[pq.top().second][i].second];
                cout << endl;
            }
        }
        pq.pop();
        Vizitat[pq.top().second] = 1;
    }
    for(int i = 2 ; i <= n ; i++)
        fout << Costuri_actuale[i] << ' ';
    return 0;
}