/*
Dijkstra cu heapuri

Complexitate: O( m * log(n) )

Observatii:
- Nodul de start a fost considerat nodul 1.
- Prima pozitie a heapului este considerata 1. Astfel, tatal nodului i va fi i/2, fiul stanga i*2, iar fiul dreapta i*2+1;
- Vectorul d memoreaza distantele minime de la 1
- Vectorul h memoreaza heap ul
- Vectorul t retine drumul de la 1 la un nod oarecare folosind memorarea de tip tata
- Vectorul poz retine pozitia fiecarui varf in heap
- La fiecare pas al algoritmului ne trebuie minimul din vectorul d si atunci intervine ideea de a organiza graful intr un minheap
pentru ca obtinerea minimului sa se faca in O(1)
- ideea minheapului este ca varful parinte sa fie mai mic decat descendentii lui, astfel cel mai mic varf va fi primul
*/

#include<fstream>
#define dim 50002
#define inf 20001

using namespace std;

struct nod
{
    int info,cost;
    nod*urm;
}*a[dim],*q; //Folosim listele pentru a evita gasirea nodurilor vecine in O(n)

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int m,n,k,h[dim],d[dim],t[dim],poz[dim],varf;

void adauga(int x,int y,int c)
{
    //facem adaugare la stanga pentru a comasa adaugare si creare
    nod *nou=new nod;
    nou->info=y;
    nou->cost=c;
    nou->urm=a[x];
    a[x]=nou;
}

void swap(int i,int j)
{
    int x;
    x=h[i];
    h[i]=h[j];
    h[j]=x;
    x=poz[h[i]];
    poz[h[i]]=poz[h[j]];
    poz[h[j]]=x;
    /*Odata cu interschimbarea a doua elemente trebuie sa interschimbam si pozitiile lor in vectorul de pozitii*/
}
void heapup(int i)
{
    //atunci cand actualizez distanta varful respectiv din heap poate sa devina mai mic decat parintele
    //si atunci il avansam prin interschimbare
    if(d[h[i/2]]<d[h[i]])return;
    swap(i,i/2);
    heapup(i/2);
}
void heapdown(int i)
{
        //cand interschimb primul varf al heapului cu ultimul, valoarea adusa pe prima pozitie poate fi mare si atunci
        //pentru a pastra prop de heap il retrogradez in stanga sau dreapta cat este nevoie
        int st,dr;
        if(i*2>m) return;
        st=d[h[i*2]];
        if(i*2+1<=m)
            dr=d[h[i*2+1]];
        else
            dr=st+1;
        if(st<dr)
        {
            if(d[h[i]]<=st)return;
            swap(i,2*i);
            heapdown(i*2);
        }
        else
        {
            if(d[h[i]]<=dr)return;
            swap(i,2*i+1);
            heapdown(2*i+1);
        }
}
void citire()
{
    int i,x,y,c;
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>x>>y>>c;
        adauga(x,y,c);
    }
}

void drum(int i)
{
    if(t[i]!=0)
    {
        drum(t[i]);
        fout<<i<<" ";
    }
    else
        fout<<"\n";//afisez un enter la final
}

int main()
{
    int i;
    citire();
    for(i=1;i<=n;i++)
    {
            d[i]=inf; /*Initial toate distantele sunt considerate infinit*/
            h[i]=i;
            poz[i]=i;
    }
    m=n;
    d[1]=0;/*Toate distantele mai putin cea a nodului initial, bineinteles*/
    d[0]=-1;/*Acest lucru este oarecum util pentru cazurile cand costul dintre doua norudi este nul si considerati 1 prima pozitie a heapului*/
    for(i=0;i<n;i++)
    {
            varf=h[1];/*Desemnam nodul pe care il expandam*/
            swap(1,m); /*Dupa ce am ales nodul pe care il vom optimiza cu dijkstra, (cel din varful heapupul) il mutam la coada*/
            m--; /* si scadem lungimea heapului, astfel incat algoritmul va lasa nodul curent in pace*/
            heapdown(1); /*Reordonam arborele*/
            for(q=a[varf];q!=NULL;q=q->urm) /*Luam fiecare nod vecin cu cel pe care il expandam*/
                    if(d[q->info]>d[varf]+q->cost) /*Verificam daca ajungem la el cu un cost mai bun*/
                    {
                            d[q->info]=d[varf]+q->cost;/*Daca da, actualizam distanta, */
                            t[q->info]=varf;/* desemnam nodul curent ca fiind noul tata al nodului pe care l-am acutalizat*/
                            heapup(poz[q->info]);/*si reordonam heapul*/
                    }
    }
    //afisarea drumurilor de la 1 (daca nu exista se afiseaza 0)
    for(i=2;i<=n;++i)
        if(d[i]==inf)
            fout<<0<<" ";
        else
            fout<<d[i]<<" ";
    fout<<"\n";
    return 0;
}