"""
p63 — Network Delay Time (LeetCode 743, MEDIUM).

Dijkstra single-source shortest path on directed graph w/ non-negative weights.
Answer = max(dist) if all reachable else -1.
"""
from __future__ import annotations
import heapq
import random
from collections import defaultdict
from typing import List, Tuple


INF = float("inf")


def network_delay_dijkstra(times: List[List[int]], n: int, k: int) -> int:
    adj: defaultdict = defaultdict(list)
    for u, v, w in times:
        adj[u].append((v, w))
    dist = [INF] * (n + 1)
    dist[k] = 0
    heap: List[Tuple[float, int]] = [(0, k)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue   # stale entry
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    m = max(dist[1:])
    return -1 if m == INF else int(m)


def network_delay_bellman_ford(times: List[List[int]], n: int, k: int) -> int:
    dist = [INF] * (n + 1)
    dist[k] = 0
    # V-1 relaxations.
    for _ in range(n - 1):
        updated = False
        for u, v, w in times:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break
    m = max(dist[1:])
    return -1 if m == INF else int(m)


def network_delay_brute(times: List[List[int]], n: int, k: int) -> int:
    # Repeated relaxation until stable (no priority); same answer.
    adj: defaultdict = defaultdict(list)
    for u, v, w in times:
        adj[u].append((v, w))
    dist = [INF] * (n + 1)
    dist[k] = 0
    changed = True
    while changed:
        changed = False
        for u in range(1, n + 1):
            if dist[u] == INF:
                continue
            for v, w in adj[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    changed = True
    m = max(dist[1:])
    return -1 if m == INF else int(m)


def edge_cases() -> None:
    assert network_delay_dijkstra([[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2) == 2
    assert network_delay_dijkstra([[1, 2, 1]], 2, 1) == 1
    assert network_delay_dijkstra([[1, 2, 1]], 2, 2) == -1   # 1 unreachable from 2
    assert network_delay_dijkstra([], 1, 1) == 0             # single node, no edges
    assert network_delay_bellman_ford([[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2) == 2
    print("edge_cases: PASS")


def stress_test() -> None:
    rng = random.Random(42)
    for trial in range(300):
        n = rng.randint(1, 7)
        m = rng.randint(0, n * (n - 1))
        times = []
        for _ in range(m):
            u = rng.randint(1, n)
            v = rng.randint(1, n)
            if u != v:
                w = rng.randint(0, 9)
                times.append([u, v, w])
        k = rng.randint(1, n)
        a = network_delay_dijkstra(times, n, k)
        b = network_delay_bellman_ford(times, n, k)
        c = network_delay_brute(times, n, k)
        assert a == b == c, f"trial {trial}: n={n} k={k} times={times} dij={a} bf={b} brute={c}"
    print("stress_test: 300 trials — Dijkstra, Bellman-Ford, brute relaxation agree.")


if __name__ == "__main__":
    edge_cases()
    stress_test()
    print("ALL TESTS PASSED")