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

const int COST_MAX = 999999;

struct Muchie
{
    int cost;
    int destinatie;

    Muchie(int cost = 0, int destinatie = 0):
        cost(cost),
        destinatie(destinatie) {}
};

struct Nod
{
    int index;
    int cost_total;
    std::vector<Muchie> muchii;

    Nod(int index = 0):
        index(index), cost_total(COST_MAX) {}
};

struct Graf
{
    int n, m;
    std::vector<Nod> noduri;

    Graf():
        n(0), m(0) {}
};

struct HeapNod
{
    int nod;
    int cost_total;

    HeapNod(int nod = 0, int cost_total = 0):
        nod(nod), cost_total(cost_total) {}
};

class HeapNodCompare
{
public:
    bool operator()(const HeapNod& a, const HeapNod& b)
    {
        return a.cost_total > b.cost_total;
    }
} heapNodeComparer;

struct Heap
{
    std::vector<HeapNod> vec;
    int len;

    HeapNod top() const { return vec[0]; }
    void push(const HeapNod& nod);
    void pop();
    void heapify();

    Heap(): len(0) {}
};

void Heap::push(const HeapNod& nod)
{
    vec.push_back(nod);
    len++;
}

void Heap::pop()
{
    std::pop_heap(vec.begin(), vec.begin() + len, heapNodeComparer);
    len--;
}

void Heap::heapify()
{
    std::make_heap(vec.begin(), vec.begin() + len, heapNodeComparer);
}

Graf* citeste_graf(const std::string& nume_fisier)
{
    std::ifstream fin(nume_fisier);
    if(!fin.is_open())
        return nullptr;

    Graf* graf = new Graf();
    int a = 0, b = 0, c = 0;

    fin >> graf->n >> graf->m;

    for(int i = 0; i < graf->n; i++)
    {
        graf->noduri.push_back(Nod(i));
    }

    for(int i = 0; i < graf->m; i++)
    {
        fin >> a >> b >> c;
        graf->noduri[a - 1].muchii.push_back(Muchie(c, b - 1));
    }

    return graf;
}

void afiseaza_graf(const Graf& graf)
{
    std::cout << graf.n << ' ' << graf.m << '\n';
    for(int i = 0; i < graf.n; i++)
    {
        for(size_t j = 0; j < graf.noduri[i].muchii.size(); j++)
        {
            std::cout << i + 1 << ' ' << graf.noduri[i].muchii[j].destinatie + 1 << ' ' << graf.noduri[i].muchii[j].cost << '\n';
        }
    }
}

void afiseaza_rezultat(const std::vector<int>& vec, size_t nod_start, const std::string& nume_fisier)
{
    std::ofstream fout(nume_fisier);
    if(!fout.is_open())
        return;

    for(size_t i = 0; i < vec.size(); i++)
    {
        if(i != nod_start)
        {
            if(vec[i] == COST_MAX)
                fout << 0 << ' ';
            else
                fout << vec[i] << ' ';
        }
    }

    fout << '\n';
}

std::vector<int> dijkstra(Graf* graf, int nod_start)
{
    std::vector<int> dist;
    Heap heap;

    for(int i = 0; i < graf->n; i++)
    {
        dist.push_back(i == nod_start ? 0 : COST_MAX);
        heap.push(HeapNod(i, dist[i]));
    }

    heap.heapify();

    while(heap.len > 0)
    {
        bool shouldHeapify = false;
        HeapNod vert = heap.top();
        heap.pop();

        for(size_t i = 0; i < graf->noduri[vert.nod].muchii.size(); i++)
        {
            int destinatie = graf->noduri[vert.nod].muchii[i].destinatie;
            int cost = graf->noduri[vert.nod].muchii[i].cost;

            int alt = dist[vert.nod] + cost;
            if(alt < dist[destinatie])
            {
                dist[destinatie] = alt;
                for(int j = 0; j < heap.len; j++)
                {
                    if(heap.vec[j].nod == destinatie)
                    {
                        heap.vec[j].cost_total = dist[destinatie];
                        shouldHeapify = true;
                        break;
                    }
                }
            }
        }

        if(shouldHeapify)
            heap.heapify();
    }

    return dist;
}

int main()
{
    Graf* graf = citeste_graf("dijkstra.in");
    std::vector<int> dist = dijkstra(graf, 0);

    afiseaza_rezultat(dist, 0, "dijkstra.out");

    delete graf;
    return 0;
}