A, B, C, D, E, F, G, H, I, J = range(10)
graf = {A: ((5, B), (3, C), (4, E)),
        B: ((5, A), (3, C), (2, F), (4, H), (3, D)),
        C: ((3, A), (3, B), (3, F), (4, G), (5, E)),
        D: ((3, B), (2, H)),
        E: ((4, A), (5, C), (4, G), (2, I)),
        F: ((3, C), (2, B), (3, H), (3, J), (4, G)),
        G: ((4, C), (4, F), (2, J), (3, I), (4, E)),
        H: ((3, F), (4, B), (2, D), (4, J)),
        I: ((2, E), (3, G), (4, J)),
        J: ((4, I), (2, G), (3, F), (4, H))
}

### Kruskalov algoritem

ceste = []
for tocka, povezave in graf.items():
    for cena, tocka2 in povezave:
        ceste.append((cena, tocka, tocka2))
ceste.sort()

mnozice = [None] * len(graf)

def find(mnozice, i):
    j = i
    while mnozice[j] != None:
        j = mnozice[j]
    while mnozice[i] != None:
        gor = mnozice[i]
        mnozice[i] = j
        i = gor
    return j

def same(mnozice, i, j):
    return find(mnozice, i) == find(mnozice, j)

def join(mnozice, i, j):
    mnozice[find(mnozice, i)] = find(mnozice, j)

povezave = []
skupna_cena = 0
for cena, tocka1, tocka2 in ceste:
    if not same(mnozice, tocka1, tocka2):
        povezave.append((tocka1, tocka2))
        skupna_cena += cena
        join(mnozice, tocka1, tocka2)


print(skupna_cena)
print(povezave)

### Primov algoritem

from heapq import heappush, heappop, heapify
povezave = []
povezane = {A}
kandidati = [(cena, A, tocka) for cena, tocka in graf[A]]
heapify(kandidati)
skupna_cena = 0
while len(povezave) < len(graf) - 1:
    cena, odkod, kam = heappop(kandidati)
    if kam in povezane:
        continue
    povezane.add(kam)
    povezave.append((odkod, kam))
    skupna_cena += cena
    for cena, naprej in graf[kam]:
        heappush(kandidati, (cena, kam, naprej))
print(skupna_cena)
print(povezave)