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

const int COST_MAX = 999999;

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

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

struct Graf
{
    Nod* noduri;
	int n, m;

	Graf(int n, int m) : n(n), m(m) { noduri = new Nod[n]; }
    ~Graf() { delete[] noduri; }
};

struct NodHeap
{
	int nod;
	int cost;
	NodHeap(int nod = 0, int cost = 0) : nod(nod), cost(cost) {}
};

struct Heap
{
	NodHeap* noduri;
	int* pozitii;
	int len;

	NodHeap top() const { return noduri[0]; }
	void push(const NodHeap& nod);
	void pop();
	void swap(int index_a, int index_b);
	bool swap_if_greater(int index_a, int index_b);
	void replace_cost(int index, int cost);

	Heap(int n) : len(0) {
	    noduri = new NodHeap[n + 1];
        pozitii = new int[n + 1];
	}

	~Heap() {
	    delete[] noduri;
        delete[] pozitii;
	}
};

Graf* citire(const std::string& nume_fisier);
void afisare(const std::string& nume_fisier, int* dist, int len);
int* dijkstra(Graf* graf, int nod_start);

int main()
{
	Graf* graf = citire("dijkstra.in");
	int* dist = dijkstra(graf, 0);

	afisare("dijkstra.out", dist, graf->n);

	delete graf;
	delete dist;
	return 0;
}

void Heap::push(const NodHeap& nod)
{
    pozitii[nod.nod] = len;
	noduri[len] = nod;
	len++;
}

void Heap::pop()
{
	swap(0, len - 1);
	len--;

	int i = 0, st = 0, dr = 0;
	do
	{
		dr = (i + 1) * 2;
		st = dr - 1;

		if(st < len)
		{
			if(dr < len)
			{
				if(noduri[dr].cost < noduri[st].cost)
				{
					if(!swap_if_greater(i, dr))
						break;

					i = dr;
				}
				else
				{
					if(!swap_if_greater(i, st))
						break;

					i = st;
				}
			}
			else
			{
				if(!swap_if_greater(i, st))
					break;

				i = st;
			}
		}
	} while(st < len);
}

void Heap::swap(int index_a, int index_b)
{
	std::swap(pozitii[noduri[index_a].nod], pozitii[noduri[index_b].nod]);
	std::swap(noduri[index_a], noduri[index_b]);
}

bool Heap::swap_if_greater(int index_a, int index_b)
{
	if(noduri[index_a].cost <= noduri[index_b].cost)
        return false;

	std::swap(pozitii[noduri[index_a].nod], pozitii[noduri[index_b].nod]);
    std::swap(noduri[index_a], noduri[index_b]);
    return true;
}

void Heap::replace_cost(int nod, int cost)
{
	int index = pozitii[nod];

	noduri[index].cost = cost;
	while(index > 0 && noduri[index].cost < noduri[(index - 1) / 2].cost)
	{
		swap(index, (index - 1) / 2);
		index = (index - 1) / 2;
	}
}

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

    int a = 0, b = 0, c = 0, n = 0, m = 0;
    fin >> n >> m;

	Graf* graf = new Graf(n, m);
	for(int i = 0; i < n; i++)
	{
		graf->noduri[i].index = i;
	}

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

	return graf;
}

void afisare(const std::string& nume_fisier, int* dist, int len)
{
	std::ofstream fout(nume_fisier);
	if(!fout.is_open())
		return;

	for(int i = 1; i < len; i++)
        fout << (dist[i] == COST_MAX ? 0 : dist[i]) << ' ';

	fout << '\n';
}

int* dijkstra(Graf* graf, int nod_start)
{
	int* dist = new int[graf->n];
	Heap heap(graf->n);

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

	while(heap.len > 0)
	{
		NodHeap 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 = vert.cost + cost;
			if(alt < dist[destinatie])
			{
				dist[destinatie] = alt;
				heap.replace_cost(destinatie, alt);
			}
		}
	}

	return dist;
}