import heapq
import itertools
import math


def dijkstra(graph, source):
    nodes = set(graph)
    for edges in graph.values():
        for target, weight in edges:
            if not math.isfinite(weight) or weight < 0:
                raise ValueError('weights must be finite and non-negative')
            nodes.add(target)
    if source not in nodes:
        raise ValueError('unknown source')
    distance = {node: math.inf for node in nodes}
    distance[source] = 0
    sequence = itertools.count()
    heap = [(0, next(sequence), source)]
    while heap:
        cost, _, vertex = heapq.heappop(heap)
        if cost != distance[vertex]:
            continue
        for target, weight in graph.get(vertex, ()):
            candidate = cost + weight
            if candidate < distance[target]:
                distance[target] = candidate
                heapq.heappush(heap, (candidate, next(sequence), target))
    return distance


if __name__ == '__main__':
    graph = {'a': [('b', 4), ('c', 1)], 'c': [('b', 1)], 'b': [], 'x': []}
    print(dijkstra(graph, 'a'))