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

struct Heap
{
	HeapNod* vec;
	int* poz;
	int len;

	HeapNod top() const { return vec[0]; }
	void push(const HeapNod& 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);
	~Heap();
};

Heap::Heap(int n) :
	len(0)
{
	vec = new HeapNod[n + 1];
	poz = new int[n + 1];
}

Heap::~Heap()
{
	delete[] vec;
	delete[] poz;
}

void Heap::push(const HeapNod& nod)
{
	vec[len] = nod;
	poz[nod.nod] = len;
	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(vec[dr].cost_total < vec[st].cost_total)
				{
					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(poz[vec[index_a].nod], poz[vec[index_b].nod]);
	std::swap(vec[index_a], vec[index_b]);
}

bool Heap::swap_if_greater(int index_a, int index_b)
{
	if(vec[index_a].cost_total > vec[index_b].cost_total)
	{
		std::swap(poz[vec[index_a].nod], poz[vec[index_b].nod]);
		std::swap(vec[index_a], vec[index_b]);
		return true;
	}

	return false;
}

void Heap::replace_cost(int nod, int cost)
{
	int index = poz[nod];
	vec[index].cost_total = cost;

	while(index > 0 && vec[index].cost_total < vec[(index - 1) / 2].cost_total)
	{
		swap(index, (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(graf->n);

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

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

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