import heapq

def shortest_path(graph, start, end):
    # Create a priority queue to store the vertices
    heap = [(0, start)]
    visited = set()
    while heap:
        (cost, current) = heapq.heappop(heap)
        if current in visited:
            continue
        visited.add(current)
        if current == end:
            return cost
        for (neighbour, weight) in graph[current].items():
            if neighbour not in visited:
                heapq.heappush(heap, (cost + weight, neighbour))
    return float("inf")

# Example graph representation
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}
}

print(shortest_path(graph, "A", "D")) # Output: 3