Infinity Handling

To represent infinity, use a large constant (e.g., $10^9$ or $10^{18}$). Do not use the maximum integer value (e.g., $2^{31}-1$), because adding two infinities can cause overflow. After Floyd-Warshall, if dist[i][j] is still infinity, there is no path from $i$ to $j$.

Choose your infinity constant based on the problem constraints. If weights are at most $10^6$ and paths have at most $n$ edges, use infinity $= 10^9$.