#include <bits/stdc++.h>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

vector <int> v[50100],d[50100];

int n,cost[50100],pozitie[50100]; // folosesc vecotrul pozitie pentru a stii unde in heap se afla nodul cu indicele "x"

struct HEAP
{
    int val,indice;
}heap[50100];

// Facem HEAP de minim

void up(int nod)
{
    if(nod/2>=1 && heap[nod/2].val>heap[nod].val)
    {
        pozitie[heap[nod].indice]=nod/2;
        pozitie[heap[nod/2].indice]=nod;

        swap(heap[nod],heap[nod/2]);
        up(nod/2);
    }
}

void down(int nod)
{
    if(2*nod+1<=n && (heap[2*nod+1].val<heap[nod].val || heap[2*nod].val<heap[nod].val))
    {
        if(heap[2*nod].val<heap[2*nod+1].val)
        {
            pozitie[heap[nod].indice]=2*nod;
            pozitie[heap[2*nod].indice]=nod;

            swap(heap[nod],heap[2*nod]);
            down(2*nod);
        }
        else
        {
            pozitie[heap[nod].indice]=2*nod+1;
            pozitie[heap[2*nod+1].indice]=nod;

            swap(heap[nod],heap[2*nod+1]);
            down(2*nod+1);
        }
    }
    else if(2*nod<=n && heap[2*nod].val<heap[nod].val)
    {
        pozitie[heap[nod].indice]=2*nod;
        pozitie[heap[2*nod].indice]=nod;

        swap(heap[2*nod],heap[nod]);
    }
}


// Algoritmul lui Dijkstra


void dijkstra(int nod)
{
    int i,j,k,val_minim,indice_minim,valoare_curenta,nod_curent,poz_in_heap,distanta_noduri;

    for(i=1;i<=n;i++)
    {
        // facem heap
        heap[i].val=INT_MAX/2;
        heap[i].indice=i;
    }

    heap[nod].val=0;
    up(nod);
    cost[nod]=0; // Pastrez distantele finale

    for(j=1;j<=n;j++)
    {
        // verific vecinii nodului cu valoarea minima, adica varful heap-ului
        val_minim=heap[1].val;
        indice_minim=heap[1].indice;

        // Merg prin toti vecinii si vad unde pot sa dau update
        for(k=0;k<v[indice_minim].size();k++)
        {
            nod_curent=v[indice_minim][k];
            valoare_curenta=cost[nod_curent];
            distanta_noduri=d[indice_minim][k]; // distanta dintre cele doua noduri

            if(distanta_noduri+val_minim < valoare_curenta) // daca am gasit un drum mai eficient decat cel deja existent
            {
                // dam update
                valoare_curenta=distanta_noduri+val_minim;
                cost[nod_curent]=valoare_curenta;

                // dam update si in heap, nodului ce are heap.indice = nod_curent
                poz_in_heap=pozitie[nod_curent];
                heap[poz_in_heap].val=valoare_curenta;
                up(poz_in_heap);
            }
        }

        // Sterg nodul deja folosit din heap
        poz_in_heap=pozitie[indice_minim];
        heap[poz_in_heap].val=INT_MAX/2;
        down(poz_in_heap);
    }

}

int m,nod1,nod2,lungime,i,j;

int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>nod1>>nod2>>lungime;
        v[nod1].push_back(nod2); // adaug vecinul
        d[nod1].push_back(lungime); // adau distanta
    }

    for(i=1;i<=n;i++)
    {
        pozitie[i]=i; // initial in heap, nodurile sunt in aceeasi ordine
        cost[i]=INT_MAX;
    }

    dijkstra(1);
    for(i=2;i<=n;i++)
    {
        if(cost[i]==INT_MAX/2) g<<0<<" "; // Nu exista drum de la nodul 1 la nodul i
        else g<<cost[i]<<" ";
    }

    return 0;
}