Bellman-Ford & Floyd-Warshall

Shortest paths when edges can be negative. Build Bellman-Ford to relax edges from a single source, detect negative-weight cycles, combine both into one safe contract, then compute all-pairs distances with Floyd-Warshall. Edges are directed tuples (u, v, w) and unreachable pairs use float('inf').