Implement floyd_warshall(n, edges) for a directed graph with nodes 0..n-1 and weighted edges (u, v, w) (weights may be negative). Return (dist, nxt), where dist[i][j] is the shortest distance (float("inf") if unreachable, and 0 on the diagonal), and nxt[i][j] is the next node after i on a shortest path to j (None if unreachable or i == j). If several edges join the same pair, use the cheapest.
Then implement:
path(nxt, i, j): the list of nodes on the shortest path from i to j, or [] if unreachable ([i] when i == j)has_negative_cycle(dist): True if any dist[i][i] < 0