#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

class muchie
{
    unsigned long nod1, nod2;
    short cost;
public:
    bool operator < (muchie m) {return cost>m.cost;};
    friend class Graf;
};

class Graf
{
    unsigned long N, M;
    struct semi {unsigned long nod; short cost; semi *urm;};
    unsigned long long distanta[50001];
    semi * G[50001];
    void push (unsigned long unde, unsigned long nod, short C);
public:
    Graf ();
    void citire();
    void dijkstra (unsigned start);
    void aff();
    ~Graf ();
};

void Graf::dijkstra (unsigned start)
{
    unsigned i, curent=start, nr=0, cost, adiacent;
    for (i=1; i<=N; i++)
        distanta[i]=1001;
    distanta[start]=0;
    muchie HEAP[M+1], muchie;
    do
    {
        //in "curent" avem ultimul nod ales
        semi *aux;
        cost=distanta[curent];
        for (aux=G[curent]; aux!=NULL; aux=aux->urm)
        {
            if (cost+aux->cost < distanta[aux->nod])
            {
                muchie.cost=aux->cost;
                muchie.nod1=curent;
                muchie.nod2=aux->nod;
                HEAP[nr]=muchie;
                nr++;
                push_heap(HEAP, HEAP+nr);
            }
        }
        //am adaugat toate muchiile noi puse de nodul curent
        //trebuie sa alegem urmatorul nod pe care il updatam
        while (nr>0 && HEAP[0].cost + distanta [HEAP[0].nod1] >= distanta[HEAP[0].nod2])
        {
            pop_heap(HEAP, HEAP+nr);
            nr--;
        }
        //acum alegand muchia HEAP[0] se updateaza urmatorul nod
        if (nr>0)
        {
            curent=HEAP[0].nod2;
            adiacent=HEAP[0].nod1;
            distanta[curent]=HEAP[0].cost+distanta[adiacent];
            pop_heap(HEAP, HEAP+nr);
            nr--;
        }
    }
    while (nr>0);
    for (i=2; i<=N; i++)
        if (distanta[i]==1001)
        distanta[i]=0;
}

void Graf::aff()
{
    unsigned i;
    ofstream f ("dijkstra.out");
    for (i=2; i<=N; i++)
        f<<distanta[i]<<' ';
}

Graf::Graf ()
{
    unsigned long i;
    for (i=1; i<=50000; i++)
        G[i]=NULL;
}

Graf::~Graf()
{
    unsigned long i;
    semi *aux;
    for (i=1; i<=N; i++)
    {
        while (G[i]!=NULL)
        {
            aux=G[i]->urm;
            delete G[i];
            G[i]=aux;
        }
    }
}

void Graf::push(unsigned long unde, unsigned long nod, short C)
{
    semi *s;
    s=new semi;
    s->cost=C;
    s->nod=nod;
    s->urm=G[unde];
    G[unde]=s;
}

void Graf::citire()
{
    ifstream f ("dijkstra.in");
    f>>N>>M;
    unsigned long i, x, y;
    short c;
    for(i=0; i<M; i++)
    {
        f>>x>>y>>c;
        push (x, y, c);
    }
}

int main()
{
    Graf G;
    G.citire();
    G.dijkstra(1);
    G.aff();
    return 0;
}