//graf orientat ponderat - drum de valoare minima - Dijkstra CU HEAP - O(n*logn)
#include <iostream>
#include <fstream>
#define N_MAX 50000
#define M_MAX 250000
#define INF 2000001
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

struct listaAd{  //structura listelor de adiacenta
//informatia utila
    int vecin;  //nodul vecin
    int cost;   //costul muchiei
//informatia de legatura
    struct listaAd *urm;
};

int n;  //numar noduri
int m;  //numar muchii

struct listaAd *L[N_MAX+2]; //vectorul cu listele de adicenta
struct listaAd *q;  //pointer-contor

int h[N_MAX+2]; //heap; heap[1] - nodul situat la ditanta minima de nodul de start
int nr; //numar noduri din heap

int viz[N_MAX+2];   //vector noduri vizitate
    //viz[i] = |pozitia_in_heap, daca nodul i e viztat/se afla in heap
    //         |0, daca nodul i e nevizitat/nu se afla in heap
int d[N_MAX+2]; //distantele de la nodul de start la nodul i

void citiri()
{
    int A,B,C;
    in>>n>>m;
    for(int i=1;i<=m;++i)
    {
        in>>A>>B>>C;
        //adauga muchia A->B de cost C la lista
        q=new listaAd;
        q->vecin=B;
        q->cost=C;
        q->urm=L[A];
        L[A]=q;
    }
}

void initDistante(int st)
{
    //distanta st->st e 0; restul sunt +INF
    for(int i=1;i<=n;++i)
        d[i]=+INF;
    d[st]=0;
}

int tata(int x){
    return x/2;
}
int fiuSt(int x){
    return x*2;
}
int fiuDr(int x){
    return x*2+1;
}

void interschimba(int &a,int &b){
    int aux;
    aux=a, a=b, b=aux;
}

void add_heap(int nod,int x)
{
//adauga nodul nod pe pozitia x in heap
    h[x]=nod;
//urca nodul la locul lui in heap
    int poz=x;  //pornim de pe pozitia x
    while(poz>1)    //cat timp exista tata
    {
        if(d[h[poz]] < d[h[tata(poz)]])    //daca distanta pana la nod e mai mica decat cea pana la tatal lui
        {
            interschimba(h[poz],h[tata(poz)]);  //interschimba nodurile in heap
            interschimba(viz[h[poz]],viz[h[tata(poz)]]);    //si pozitiile acestora
            poz=tata(poz);
        }
        else    //altfel nodul se afla la locul lui
            poz=1;  //oprim procesul
    }
}

void delete_heap(int x)
{
//sterge nodul din heap de pe pozitia x
    h[x]=h[nr]; //suprapune ultimul nod peste nodul x
    //interschimba(h[x],h[nr]);
    interschimba(viz[h[x]],viz[h[nr]]);
    nr=nr-1;
//coboara nodul la locul lui in heap
    int poz=x;  //pornim de pe pozitia x
    while(poz<=nr/2) //cat timp exista fii
    {
        int fiu = fiuSt(poz);   //retine pozitia fiuluiStanga
        if(fiu+1<=nr)   //daca exista fiuDreapta
            if(d[h[fiuDr(poz)]] < d[h[fiu]])    //si distanta pana la fiuDr e mai mica decat cea pana la fiuSt
                fiu = fiuDr(poz);   //retine pozitia fiuluiDreapta

        if(d[h[poz]] > d[h[fiu]])    //daca distanta pana la nod e mai mare ca cea pana la fiu
        {
            interschimba(h[poz],h[fiu]);    //interschimba nodurile in heap
            interschimba(viz[h[poz]],viz[h[fiu]]);  //si pozitiile acestora
            poz=fiu;
        }
        else    //altfel nodul se afla la locul sau
            poz=nr/2+1;  //incheie procesul
    }
}

void dijkstra(int st)
{
//adauga in heap vecinii nodului de start
    nr=0;
    q=L[st];
    while(q!=NULL)  //parcurge lista nodului de start
    {
        //actualizeaza distanta
        d[q->vecin]=q->cost;
        //adauga vecinul in heap
        nr=nr+1;
        viz[q->vecin]=nr;
        add_heap(q->vecin,nr);
        //ia urmatorul vecin
        q=q->urm;
    }

//ia urmatoarele noduri vecine si actualizeaza ditantele daca e cazul
    while(nr>0) //cat timp heapul nu e vid
    {
        int minim = h[1];   //extrage primul nod din heap
        viz[minim]=0;
        delete_heap(1); //sterge primul nod din heap
        //ia toti vecinii nodului extras
        q=L[minim];
        while(q!=NULL)
        {
            if(d[q->vecin] > d[minim]+q->cost)
            {
                d[q->vecin] = d[minim]+q->cost;
                if(viz[q->vecin]==0)    //daca vecinul se afla in heap
                {
                    //adauga vecinul la finalul heapului si actualizeaza
                    nr=nr+1;
                    viz[q->vecin]=nr;
                    add_heap(q->vecin,nr);
                }
                else    //altfel (vecinul nu se afla in heap)
                {
                    //actualizeaza heap
                    add_heap(q->vecin,viz[q->vecin]);
                }
            }
            q=q->urm;
        }
    }
}

void afisDistante()
{
    for(int i=2;i<=n;++i)
    {
        if(d[i]!=INF)
            out<<d[i]<<" ";
        else
            out<<"0 ";
    }
    out<<"\n";
}

int main()
{
    citiri();
    initDistante(1);
    dijkstra(1);
    afisDistante();

    return 0;
}