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

using namespace std;

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

class Graf
{
    unsigned long N, M;
    struct semi {unsigned long nod; unsigned long cost; semi *urm;};
    vector <unsigned long long> distanta;
    vector <semi *> G;
    void push (unsigned long unde, unsigned long nod, unsigned long C);
public:
    //Graf ();
    void citire();
    void dijkstra (unsigned start);
    void aff();
    ~Graf ();
};

void Graf::dijkstra (unsigned start)
{
    unsigned i, curent=start, cost, adiacent;
    distanta.push_back(0);
    for (i=1; i<=N; i++)
        distanta.push_back(500000000);
    distanta[start]=0;
    vector<muchie> HEAP;
    muchie mch;
    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])
            {
                mch.cost=aux->cost;
                mch.nod1=curent;
                mch.nod2=aux->nod;
                HEAP.push_back(mch);
                push_heap(HEAP.begin(), HEAP.end());
            }
        }
        //am adaugat toate muchiile noi puse de nodul curent
        //trebuie sa alegem urmatorul nod pe care il updatam
        while (!HEAP.empty() && HEAP[0].cost + distanta [HEAP[0].nod1] >= distanta[HEAP[0].nod2])
        {
            pop_heap(HEAP.begin(), HEAP.end());
            HEAP.pop_back();
        }
        //acum alegand muchia HEAP[0] se updateaza urmatorul nod
        if (!HEAP.empty())
        {
            curent=HEAP[0].nod2;
            adiacent=HEAP[0].nod1;
            distanta[curent]=HEAP[0].cost+distanta[adiacent];
            pop_heap(HEAP.begin(), HEAP.end());
            HEAP.pop_back();
        }
    }
    while (!HEAP.empty());
    HEAP.clear();
    for (i=2; i<=N; i++)
        if (distanta[i]==500000000)
        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;
    semi *aux;
    for (i=1; i<=N; i++)
    {
        while (G[i]!=NULL)
        {
            aux=G[i]->urm;
            delete G[i];
            G[i]=aux;
        }
    }
    G.clear();
    distanta.clear();
}

void Graf::push(unsigned long unde, unsigned long nod, unsigned long 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;
    unsigned long c;
    for (i=0; i<=N; i++)
        G.push_back(NULL);
    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;
}