#include <fstream>

#define NMAX 50001

struct Elem
{
    int nod, lungime;
};

struct Adiacenta
{
    Elem arc;
    Adiacenta *urm;
};

std::ifstream f("dijkstra.in");
std::ofstream g("dijkstra.out");
Adiacenta *Lista[NMAX];
Elem Heap[NMAX];
int N, M, H_Dim, dist[NMAX], Viz[NMAX];

void citire()
{
    f >> N >> M;
    int A, B, C;
    for(int i = 1; i <= M; i++)
    {
        f >> A >> B >> C;

        Adiacenta *aux = new Adiacenta;
        aux->arc.nod = B;
        aux->arc.lungime = C;
        aux->urm = Lista[A];
        Lista[A] = aux;
    }
    f.close();
}

void afisare()
{
    for(int i = 2; i <= N; i++)
    {
        if(dist[i] != 30000)
            g << dist[i] << ' ';
        else
            g << 0 << ' ';
    }
    g.close();
}
void InserareHeap(int vf, int lung)
{
    Elem inserat;
    inserat.nod = vf;
    inserat.lungime = lung;
    Heap[++H_Dim] = inserat;

    int prt_idx = H_Dim / 2;
    int ins_idx = H_Dim;
    while(Heap[prt_idx].lungime > Heap[ins_idx].lungime && prt_idx != 0)
    {
        Heap[ins_idx] = Heap[prt_idx];
        Heap[prt_idx] = inserat;

        ins_idx = prt_idx;
        prt_idx /= 2;
    }
}

Elem ExtragereHeap()
{
    Elem Ext = Heap[1];

    Heap[1] = Heap[H_Dim--];
    int fiu_idx = 2;
    while(fiu_idx <= H_Dim)
    {
        if(fiu_idx + 1 <= H_Dim && Heap[fiu_idx].lungime > Heap[fiu_idx + 1].lungime)
            fiu_idx++;

        int prt_idx = fiu_idx / 2;
        if(Heap[prt_idx].lungime > Heap[fiu_idx].lungime)
        {
            Elem aux = Heap[prt_idx];
            Heap[prt_idx] = Heap[fiu_idx];
            Heap[fiu_idx] = aux;
            fiu_idx *= 2;
        }
        else
            break;
    }
    return Ext;
}

void Dijkstra(int nod_start)
{
    for(int i = 2; i <= N; i++)
        dist[i] = 30000;

    InserareHeap(nod_start, 0);
    do
    {
        Elem NodActual = ExtragereHeap();
        if(Viz[NodActual.nod] == 0)
        {
            Adiacenta *it = Lista[NodActual.nod];
            while(it != NULL)
            {
                if(Viz[it->arc.nod] == 0 && dist[it->arc.nod] > dist[NodActual.nod] + it->arc.lungime)
                {
                    dist[it->arc.nod] = dist[NodActual.nod] + it->arc.lungime;
                    InserareHeap(it->arc.nod, dist[it->arc.nod]);
                }
                it = it->urm;
            }
            Viz[NodActual.nod] = 1;
        }
    }while(H_Dim != 0);
}

int main()
{
    citire();
    Dijkstra(1);
    afisare();
    return 0;
}