from __future__ import annotations

import heapq
from itertools import count
from math import inf
from typing import Hashable, Iterable, Mapping, TypeVar

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


def dijkstra(
    graph: Graph[Node], start: Node
) -> tuple[dict[Node, float], dict[Node, Node | None]]:
    """Return shortest distances and predecessors from start."""
    distances = {node: inf for node in graph}
    predecessors: dict[Node, Node | None] = {node: None for node in graph}
    distances[start] = 0.0

    # The counter avoids comparing nodes when heap priorities are equal.
    tie_breaker = count()
    queue: list[tuple[float, int, Node]] = [(0.0, next(tie_breaker), start)]

    while queue:
        distance, _, node = heapq.heappop(queue)
        if distance != distances[node]:
            continue

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

            candidate = distance + weight
            if candidate < distances.get(neighbor, inf):
                distances[neighbor] = candidate
                predecessors[neighbor] = node
                heapq.heappush(
                    queue, (candidate, next(tie_breaker), neighbor)
                )

    return distances, predecessors


def shortest_path(
    graph: Graph[Node], start: Node, target: Node
) -> tuple[float, list[Node]]:
    """Return the shortest distance and path from start to target."""
    distances, predecessors = dijkstra(graph, start)
    if distances.get(target, inf) == inf:
        return inf, []

    path = [target]
    while path[-1] != start:
        predecessor = predecessors[path[-1]]
        if predecessor is None:
            return inf, []
        path.append(predecessor)

    path.reverse()
    return distances[target], path


def _run_tests() -> None:
    graph = {
        "A": [("B", 4), ("C", 1)],
        "B": [("D", 1)],
        "C": [("B", 2), ("D", 5)],
        "D": [],
        "E": [],
    }

    assert shortest_path(graph, "A", "D") == (4.0, ["A", "C", "B", "D"])
    assert shortest_path(graph, "A", "E") == (inf, [])


if __name__ == "__main__":
    _run_tests()
    print("All tests passed.")