Recently I came across a problem (https://algs4.cs.princeton.edu/44sp/ question #34). I've already devised an algorithm that modifies Dijkstra's algorithm under the assumption that the graph only has positive weights. I was wondering, how would I go about modifying Bellman-Ford (or some other negative weight shortest path algorithm) to solve this problem in $$$O(n^2m)$$$ time?

Note: I also saw something similar in CLRS (bitonic shortest paths), but the solution found here: https://walkccc.me/CLRS/Chap24/Problems/24-6/ is a extremely difficult to understand.