/*
Radu Sorin Gabriel
Grupa 134
Semigrupa 1
*/
#include <iostream>
#include <algorithm>
#include <fstream>
#include <functional>
#include <vector>
#define INT_MAX 0x3f3f3f3f
using namespace std;
/// Structura pentru a retine extremitatea dreapta si costul unei muchii.
struct muchie
{
    int dr,cost;
};
ifstream fin;
ofstream fout;
int n,k;
int *d = NULL,*control = NULL;
/// Functie pentru constructia si mentinerea min-heap-ului.
struct f
{
    bool operator()(int i,int j)
    {
        return d[j] < d[i];
    }
};
int predecesor(int x,int *pred)
{
    /// Daca x nu este nodul sursa,ma duc recursiv la tatal lui x,pana ajung la nodul sursa si la intoarcere din recursivitate scriu nodurile care formeaza drumul.
    if (x != -1)
    {
        predecesor(pred[x],pred);
    }
    return 0;
}
void Dijkstra(vector <struct muchie> *v,int s)
{
    int tata[n];
    d = new int [n];
    /// Initializez vectorul de tati cu 0 si cel de distante cu infinit.
    for (int i=0; i<n; i++)
    {
        d[i] = INT_MAX;
        tata[i] = 0;
    }
    /// Pentru nodul sursa distanta este 0,iar tatal lui este -1 (nu exista).
    d[s] = 0;
    tata[s] = -1;
    /// Fac un vector heap cu etichetele nodurilor.
    vector <int> heap;
    for (int i=0; i<n; i++)
        heap.push_back(i);
    /// Cu ajutorul functiei f fac un min-heap cu nodurile din heap avand ca si criteriu de constructie distanta de la sursa la nodul respectiv.
    make_heap(heap.begin(),heap.end(),f());
    /// Pana cand heap-ul este gol,il decapitez.
    while (heap.size() != 0)
    {
        /// Extrag radacina heap-ului.
        int x = heap.front();
        /// Ma duc la vecinii nodului scos din heap si vad daca pot relaxa muchia.
        for (int i=0; i<v[x].size(); i++)
            if (d[x] + v[x][i].cost < d[v[x][i].dr])
            {
                /// Daca se poate relaxa muchia,actualizez distanta.
                d[v[x][i].dr] = d[x] + v[x][i].cost;
                /// Marchez ca tatal vecinului lui x sa fie x.
                tata[v[x][i].dr] = x;
            }
        /// Sterg radacina din heap pastrand proprietatile min-heapului.
        pop_heap(heap.begin(),heap.end(),f());
        heap.pop_back();
    }
    /// Caut punctul de control care are distanta minima fata de sursa.
    int minim = INT_MAX,nod = 0;

    /// Afisez cel mai apropiat punct de control de nodul sursa si drumul pana la acesta (folosind vectorul de tati,ma duc din tata in tata).
   for(int i = 1 ; i < n ; ++i)
        fout<<d[i]<<' ';
    delete []d;
    return;
}
int main()
{
    int m,x,y,cost,s;
    fin.open("dijkstra.in");
    fin >> n >> m;
    /// Construiesc lista de adiacenta.
    vector <struct muchie > v[n];
    for (int i=0; i<m; i++)
    {
        fin >> x >> y >> cost;
        struct muchie a;
        a.dr = y - 1;
        a.cost = cost;
        v[x-1].push_back(a);
        a.dr = x - 1;
        v[y-1].push_back(a);
    }
    fin.close();
    /// Citesc cele k puncte de control.
    /// Citesc nodul sursa.
    s=1;
    fout.open("dijkstra.out");
    /// Aplic Dijkstra pentru nodul sursa.
    Dijkstra(v,s-1);



    return 0;
}