def heap_insert(pole, prvek):
	pole.append(prvek)
	index = len(pole) - 1 # index nove pridaneho prvku
	heap_decrease(pole, index)

def heap_extract_min(pole):
	vysledek = pole[0]
	if len(pole) > 1:
		# pokud v poli neco zbylo, musime ho zkontrolovat a opravit
		pole[0] = pole.pop()
		novy = 0;
		while 2*novy + 2 < len(pole): # dokud ma prvek oba syny
			levy_syn  = 2*novy + 1
			pravy_syn = 2*novy + 2
			mensi_syn = levy_syn if pole[levy_syn] < pole[pravy_syn] else pravy_syn
			if pole[novy] < pole[mensi_syn]:
				# uz je vsechno v poradku
				break
			# jinak prvky prohodime
			pole[novy], pole[mensi_syn] = pole[mensi_syn], pole[novy]
			pole[novy].index_v_halde = novy
			novy = mensi_syn # a vyresime situaci o vrstvu nize
		if 2*novy + 2 == len(pole):
			# specialni pripad, pokud ma prvek jen jedineho syna (a ten je tedy na konci pole)
			levy_syn = 2*novy + 1
			if pole[levy_syn] < pole[novy]:
				pole[novy], pole[levy_syn] = pole[levy_syn], pole[novy]
				pole[novy].index_v_halde = novy
				novy = levy_syn
		pole[novy].index_v_halde = novy
	else:
		pole.pop()
	vysledek.index_v_halde = None
	return vysledek

def heap_decrease(pole, index):
	while index > 0: # dokud se nedostaneme do korene
		otec = (index-1) // 2; 
		if pole[otec] < pole[index]:
			# vsechno je v poradku
			break
		pole[index], pole[otec] = pole[otec], pole[index]
		pole[index].index_v_halde = index
		index = otec # a vyresime situaci o vrstvu vys
	pole[index].index_v_halde = index


class Vrchol:
	def __init__(self, cislo):
		self.hrany = dict()
		self.index_v_halde = None
		self.vzdalenost = None # tohle bude znamenat nekonecnou vzdalenost
		self.jmeno = chr(ord("A") + cislo)
	def __lt__(self, other): # navraci vysledek porovnavani (self < other)
		return self.vzdalenost < other.vzdalenost

def dijkstra(start):
	halda = []
	start.vzdalenost = 0
	heap_insert(halda, start)
	while halda:
		vrchol = heap_extract_min(halda)
		for konec, delka in vrchol.hrany.items():
			if konec.vzdalenost is None:
				konec.vzdalenost = vrchol.vzdalenost + delka
				heap_insert(halda, konec)
			elif vrchol.vzdalenost + delka < konec.vzdalenost:
				konec.vzdalenost = vrchol.vzdalenost + delka
				heap_decrease(halda, konec.index_v_halde)

a, b, c, d, e, f = graf = [Vrchol(i) for i in range(6)]
for x, y, delka in ((a, b, 1), (a, c, 1), (b, d, 2), (b, e, 4), (c, d, 3), (c, e, 5), (d, e, 1), (d, f, 4), (e, f, 3)):
	x.hrany[y] = delka
	y.hrany[x] = delka

dijkstra(a)
for vrchol in graf:
	print ("do vrcholu {} je to daleko {}.".format(vrchol.jmeno, vrchol.vzdalenost))