import random

povezave = {
    "Krk": {"Goli": 2, "Rab": 5, "Cres": 4},
    "Goli": {"Krk": 2, "Rab": 1, "Olib": 5, "Pag": 2},
    "Rab": {"Krk": 5, "Goli": 1, "Olib": 3, "Cres": 3},
    "Cres": {"Krk": 4, "Rab": 3, "Ist": 5},
    "Pag": {"Goli": 2, "Olib": 4, "Pašman": 5},
    "Olib": {"Rab": 3, "Goli": 5, "Pag": 4, "Iž": 4, "Dugi": 4, "Ist": 2},
    "Ist": {"Cres": 5, "Olib": 2, "Dugi": 1},
    "Pašman": {"Pag": 5, "Iž": 4, "Murter": 4},
    "Iž": {"Olib": 4, "Pašman": 4, "Dugi": 2},
    "Dugi": {"Ist": 1, "Olib": 4, "Iž": 2},
    "Murter": {"Pašman": 4}
}

# e povezav
def dijkstra(zacetek, konec):
    vemo = {}     # ključ: otok, vrednost: minimalna cena do otoka, odkod
    kandidati = [None, (0, "Krk", None)]
    while konec not in vemo:
        cena, otok, odkod = pop(kandidati)
        if otok in vemo:
            continue
        vemo[otok] = (cena, odkod)
        for nasl, cena_povezave in povezave[otok].items():
            push(kandidati, (cena + cena_povezave, nasl, otok))

    pot = [konec]
    while pot[-1] != zacetek:
        pot.append(vemo[pot[-1]][1])

    return pot[::-1], vemo[konec][0]

def pop(kopica):
    m = kopica[1]
    kopica[1] = kopica[-1]
    del kopica[-1]

    i = 1
    while 2 * i < len(kopica):
        j = 2 * i
        if j + 1 < len(kopica) and kopica[j + 1] < kopica[j]:
            j += 1
        if kopica[i] > kopica[j]:
            kopica[i], kopica[j] = kopica[j], kopica[i]
            i = j
        else:
            break
    return m

def push(kopica, n):
    kopica.append(n)
    i = len(kopica) - 1
    while i > 1 and kopica[i // 2] > kopica[i]:
        kopica[i // 2], kopica[i] = kopica[i], kopica[i // 2]
        i //= 2


print(dijkstra("Krk", "Dugi"))