/*se da un graf orientat si se cunosc numarul de noduri, de arce si costurile lor
se cere lungimea minima de la nodul 1 la toate celelalte
algoritmul lui dijkstra

d[i] lungimea minima a drumului de la 1 la i
s[i] 1 daca i a fost folosit , 0 contrar
t[i]=j j este predecesorul lui i in drumul minim de la 1

memorarea se va face cu listele de adiacenta. Informatia va fi retinuta cu doua campuri unul pentru nod si altul ptr cost
listele vor fi alocate dinamic simplu inlantuit
vom da functie  pentru adaugarea unui nod la lista corespunzatoare
a[x]->info va fi arcul (x,info), iar a[x]->cost va fi costul arcului

initializez toate componentele lui d cu infinit mai putin prima(nodul 1 este de plecare)
initializez toate componentele lui t cu 0(direct din declarare) mai putin cele care au arc pornind din 1
De exemplu t[2]=1 exista arcul (1,2)
pentru fiecare nod, calculez minimul valorilor utile ale lui d si vad daca drumul de la 1 la acel nod nu poate fi rafinit
trecand prin noduri intermediare
daca d[pozmin]>d[j]+lungimea arcului de la pozmin la j atunci
    d[pozmin]=d[j]+lungimea
Daca drumul s a putut rafina retin t[j]=pozmin pentru a putea reconstitui drumul
Functia drum reconstituie drumul mergand de la varful caruia vrem sa i afisam drumul minim pana la 1
in aceasta problema se cer doar lungimile drumurilor, nu vom afisa efectiv drumurile
*/
#include <fstream>
#include<vector>
#define dim 50002
#define inf 20001

using namespace std;

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

struct nod
{
    int info,cost;
    nod*urm;
};

nod *a[dim];
int d[dim],s[dim],t[dim],n,m;

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 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
}

void dijkstra()
{
    int min,i,j,pozmin;
    pozmin=0;
    for(i=2;i<=n;++i)
        d[i]=inf;

    nod*parc=a[1];
    while(parc!=NULL)
    {
        t[parc->info]=1;
        parc=parc->urm;
    }

    for(i=1;i<=n;++i)
    {
        //calculez minimul lui d si pozitia, se iau in considerare doar varfurile neparcurse
        min=inf;
        for(j=1;j<=n;++j)
            if(s[j]==0 && d[j]<min)
                min=d[j],pozmin=j;
        //marchez pozmin ca fiind parcurs
        s[pozmin]=1;
        //rafinez drumul cercetand daca poate trece prin varfuri intermediare
        //varfurile vor fi parcurse din lista lui pozmin
        parc=a[pozmin];
        while(parc!=NULL)
        {
            if(d[parc->info]>d[pozmin]+parc->cost)
                d[parc->info]=d[pozmin]+parc->cost,t[parc->info]=pozmin;
            parc=parc->urm;
        }

    }
}
int main()
{
    int i;
    citire();
    dijkstra();
    //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;
}