A weighted graph with different edge weights needs a different tool: BFS counts edges, not weights. Dijkstra's algorithm finds the shortest paths from one start vertex to all others when all weights are non-negative. Graphs are stored as in Graph Representations: graph[u] is a list of pairs (v, w).

A weighted graph and the trace of Dijkstra from A
A weighted graph and the trace of Dijkstra from A

The idea

For every vertex dist keeps the best distance known so far: 0 for the start, ∞ for the others. At every step the algorithm takes the not yet final vertex u with the smallest dist. The weights are non-negative, so no shorter path to u can appear later: dist[u] is final. Then every edge u -> v is relaxed: if dist[u] + w < dist[v], we update dist[v]. A min-heap finds the smallest dist quickly.

Implementation with heapq

The heap holds pairs (distance, vertex). heapq has no decrease-key operation, so on an improvement we simply push a new pair, and a stale pair is discarded when popped by the check d > dist[u].

python
INF = float("inf")
graph = {
    "A": [("B", 7), ("C", 9), ("F", 14)],
    "B": [("A", 7), ("C", 10), ("D", 15)],
    "C": [("A", 9), ("B", 10), ("D", 11), ("F", 2)],
    "D": [("B", 15), ("C", 11), ("E", 6)],
    "E": [("D", 6), ("F", 9)],
    "F": [("A", 14), ("C", 2), ("E", 9)],
}

import heapq