def dijkstra(graph, from_node, to_node):

    q, seen = [(0, from_node, [])], set()

    while q:

        cost, node, path = heappop(q)

        seen.add(node)

        path = path+[node]

        if node == to_node:

            return cost,path

        for adj_node, c in graph.get(node, {}).items():

            if adj_node not in seen:

                heappush(q, (cost+c, adj_node, path))

    return -1,[]

air_lines = {"1":{"2":2000, "3":2000, "4":4000, "5": 4500}, "2":{"5": 1000}, "3":{"4": 1000}, "4":{"5": 500}}

print(dijkstra(air_lines, "1", "4"))

print(dijkstra(air_lines, "1", "5"))

print(dijkstra(air_lines, "4", "5"))

print(dijkstra(air_lines, "5", "4"))

print(dijkstra(air_lines, "1", "1"))

print(dijkstra(air_lines, "10", "10"))

"""

(3000, ['1', '3', '4'])

(3000, ['1', '2', '5'])

(500, ['4', '5'])

(-1, [])

(0, ['1'])

(0, ['10'])

"""