Solve using Floyd-Warshall algorithm with a special case of containing a negative cycle.

https://cp-algorithms.com/graph/all-pair-shortest-path-floyd-warshall.html

If there exists a negative cycle, running the algorithm two times will produce lower distance than running it once (or as the blog says, the distance from a vertex to itself will be negative).

I advise you read the algorithm first, then handle the case with negative cycles.