def dijkstra(graph, s):
    dist = {}

    for v in graph:
        dist[v] = float('inf')

    dist[s] = 0

    S = set()
    Q = list(graph.keys())

    while Q:
        u = min(Q, key=lambda x: dist[x])

        Q.remove(u)
        S.add(u)

        for v, w in graph[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w

    return dist


# Example Graph
graph = {
    'A': [('B', 4), ('C', 1)],
    'B': [('D', 1)],
    'C': [('B', 2), ('D', 5)],
    'D': []
}

s = 'A'

dist = dijkstra(graph, s)

for v in dist:
    print(v, ":", dist[v])