from __future__ import annotations

import heapq
from collections.abc import Hashable, Mapping, Sequence
from itertools import count
from typing import TypeVar

Node = TypeVar("Node", bound=Hashable)
Graph = Mapping[Node, Sequence[tuple[Node, float]]]


def dijkstra(graph: Graph[Node], start: Node, goal: Node) -> tuple[float, list[Node]]:
    """Return the shortest distance and path from start to goal."""
    distances: dict[Node, float] = {start: 0.0}
    previous: dict[Node, Node] = {}
    visited: set[Node] = set()

    # A counter avoids comparing node values when heap priorities tie.
    tie_breaker = count()
    heap: list[tuple[float, int, Node]] = [(0.0, next(tie_breaker), start)]

    while heap:
        current_distance, _, current = heapq.heappop(heap)

        if current in visited:
            continue
        visited.add(current)

        if current == goal:
            return current_distance, _reconstruct_path(previous, start, goal)

        for neighbor, weight in graph.get(current, ()):
            if weight < 0:
                raise ValueError("Dijkstra's algorithm requires non-negative weights")

            new_distance = current_distance + weight
            if new_distance < distances.get(neighbor, float("inf")):
                distances[neighbor] = new_distance
                previous[neighbor] = current
                heapq.heappush(heap, (new_distance, next(tie_breaker), neighbor))

    return float("inf"), []


def _reconstruct_path(previous: dict[Node, Node], start: Node, goal: Node) -> list[Node]:
    path = [goal]
    current = goal

    while current != start:
        current = previous[current]
        path.append(current)

    path.reverse()
    return path


def _run_tests() -> None:
    graph: dict[str, list[tuple[str, float]]] = {
        "A": [("B", 4), ("C", 2)],
        "B": [("C", 1), ("D", 5)],
        "C": [("B", 1), ("D", 8), ("E", 10)],
        "D": [("E", 2)],
        "E": [],
    }

    assert dijkstra(graph, "A", "D") == (7.0, ["A", "C", "B", "D"])
    assert dijkstra(graph, "A", "E") == (9.0, ["A", "C", "B", "D", "E"])
    assert dijkstra(graph, "E", "A") == (float("inf"), [])


if __name__ == "__main__":
    _run_tests()