#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)
	{
		if(a.cost_total == b.cost_total)
			return a.nod > b.nod;

		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();
	void replace_cost(int index, int cost);

	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);
}

void Heap::replace_cost(int index, int cost)
{
	vec[index].cost_total = cost;
	while(index > 0 && vec[index].cost_total < vec[(index - 1) / 2].cost_total)
	{
		std::swap(vec[index], vec[(index - 1) / 2]);
		index = (index - 1) / 2;
	}
}

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]));
	}

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

		bool found = false;

		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;
				found = true;
			}
		}

		if(found)
		{
			for(int i = 0; i < heap.len; i++)
			{
				if(heap.vec[i].cost_total != dist[heap.vec[i].nod])
				{
					heap.replace_cost(i, dist[heap.vec[i].nod]);
				}
			}
		}
	}

	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;
}