Halum
Apply some operations on arcs to make vertex weights non-negative.
This is a negative cycle detection problem
First observe that the operations Halum commute. The order in which they are applied does not matter and there is no need to apply it twice for a same vertex.
Let K be the lower bound on the arc weights we want to obtain. Suppose that we call Halum(v,d[v]) for some values d[v] on every vertex v. This means that we have the following lower bound on the arc weights:
w[u,v]+d[u]-d[v]≥K
Does it ring a bell? This is exactly the inequality that appears in the shortest path problem. Hence for fixed K the goal is to find potentials d that satisfy these inequalities for a graph with arc weights w[u,v]-K. It is known that there is a solution if and only if the graph has no negative cycle. To convince yourself just notice that if you add up the arc inequalities along a cycle, the potentials cancel out and you are left with an equality stating that the total arc weights along the cycle have to be non-negative.
So you could just run a negative cycle detection algorithm for a fixed K, and use binary search to detect the optimal K. The domain of K is [-|V|*10000,+|V|*10000], so the binary search stops after \(log_2(10^{7})\leq 24\) iterations.
A sample code can be found here.