#include <fstream>

#define NMAX 50001

struct Adiacenta
{
    int nod;
    int lungime;
    Adiacenta *urm;
};

std::ifstream f("dijkstra.in");
std::ofstream g("dijkstra.out");
Adiacenta *Lista[NMAX];
int Heap[NMAX];
int N, M, H_Dim, dist[NMAX], PozInHeap[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->nod = B;
        aux->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 ins_idx;
    if(PozInHeap[vf] != 0)
        ins_idx = PozInHeap[vf];
    else
    {
        Heap[++H_Dim] = vf;
        ins_idx = H_Dim;
    }
    int prt_idx = ins_idx / 2;
    while(dist[ Heap[prt_idx] ] > dist[ Heap[ins_idx] ] && prt_idx != 0)
    {
        int aux = Heap[ins_idx];
        Heap[ins_idx] = Heap[prt_idx];
        Heap[prt_idx] = aux;

        ins_idx = prt_idx;
        prt_idx /= 2;
    }
    PozInHeap[vf] = ins_idx;
}

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

    Heap[1] = Heap[H_Dim--];

    int prt_idx = 1;
    int fiu_idx = 2;
    while(fiu_idx <= H_Dim)
    {
        if(fiu_idx + 1 <= H_Dim && dist[ Heap[fiu_idx] ] > dist[ Heap[fiu_idx + 1] ])
            fiu_idx++;

        if(dist[ Heap[prt_idx] ] > dist[ Heap[fiu_idx] ])
        {
            int aux = Heap[prt_idx];
            Heap[prt_idx] = Heap[fiu_idx];
            Heap[fiu_idx] = aux;

            prt_idx = fiu_idx;
            fiu_idx *= 2;
        }
        else
            break;
    }
    PozInHeap[ Heap[prt_idx] ] = prt_idx;

    return Ext;
}

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

    InserareHeap(nod_start);
    while(H_Dim != 0)
    {
        int NodActual = ExtragereHeap();
        Adiacenta *vecin = Lista[NodActual];
        while(vecin != NULL)
        {
            if(PozInHeap[vecin->nod] != -1 && dist[vecin->nod] > dist[NodActual] + vecin->lungime)
            {
                dist[vecin->nod] = dist[NodActual] + vecin->lungime;
                InserareHeap(vecin->nod);
            }
            vecin = vecin->urm;
        }
        PozInHeap[NodActual] = -1;
    }
}

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