import heapq
graph = {
  'A': [('B',1),('C',4)], 'B': [('A',1),('C',2),('D',5)],
  'C': [('A',4),('B',2),('D',1)], 'D': [('B',5),('C',1)]
}
dist = {n: float('inf') for n in graph}
dist['A'] = 0
pq = [(0, 'A')]
while pq:
    d, u = heapq.heappop(pq)
    if d > dist[u]: continue
    for v, w in graph[u]:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            heapq.heappush(pq, (dist[v], v))
print(dist['D'])