
import math

INFINI = math.inf
NEIGHBOURS = "neighbours"

def dijkstra(graph, origin, destination=None):
    distances = {}
    ancestors = {}
    unknown = {}
    path = []
    finish = False
    for city in graph:
        unknown[city] = True
        ancestors[city] = origin
        if city in graph[origin][NEIGHBOURS]:
            distances[city] = graph[origin][NEIGHBOURS][city]
        else:
            distances[city] = INFINI
    distances[origin] = 0
    unknown[origin] = False
    new_city = origin
    while not finish:
        minimum = INFINI
        for city in graph:
            if unknown[city] and distances[city] < minimum:
                new_city = city
                minimum = distances[city]
        if minimum == INFINI:
            finish = True
        unknown[new_city] = False
        for town in graph[new_city][NEIGHBOURS]:
            if distances[new_city] + graph[new_city][NEIGHBOURS][town] < distances[town]:
                distances[town] = distances[new_city] + graph[new_city][NEIGHBOURS][town]
                ancestors[town] = new_city
    if (destination is not None) and (distances[destination] != INFINI):
        city = destination
        while city != origin:
            path.append(city)
            city = ancestors[city]
        path.append(origin)
        path.reverse()
    return [distances, path]