First, let us create a graph in the following manner: if person ~A~ owes money to person ~B~, we create a directed edge from vertex ~A~ to ~B~ with cost ~C~. One important property of such a graph is that every vertex has outdegree equal to ~1~ (indegree varies).

Further, let us assume that graph is connected - if we know a solution for such a graph, we can solve the general graph case by solving each component separately and summing the results.

Looking at one component we can observe that exists exactly one cycle. We can prove that by induction. Base of the induction is a component with ~2~ vertices. It is obvious that it contains one cycle. Let us now assume that this claim is true for every component which contains ~N~ vertices. If we now look at a component with ~N+1~ vertices, we can observe that there are two cases - if the indegree of each vertex is equal to ~1~ it is trivial to show that all of the ~N+1~ vertices form a cycle. If there is a vertex with indegree equal to zero, we can erase that vertex - now we have a component with ~N~ vertices which does contain a cycle (according to induction).

Each vertex with indegree of zero has to get the amount of money equal to the total debt of the corresponding person. After that step, we can erase each such vertex, but we keep track that neighbor vertices now have a starting budget. These steps are repeated until there are no more vertices with indegree of zero (notice that by erasing a vertex, we change indegree of neighboring vertices).

At this point, there is only one cycle remaining. If there is a vertex which has enough money to return its debt, we return its debt and erase its outgoing edges. Solution for the case when no such vertex exists is described in the next paragraph.

For every vertex ~X~ we will compute how much money it must get from the city after it gets money from its debtor which lies on the cycle - let ~f(X)~ denote that amount. We will donate that amount to every vertex ~X~ on the cycle, except for the one from which debt-returning-chain-reaction is started - that vertex will get the amount it needs, assuming that it gets no money from its debtor - let ~g(X)~ denote that number. If ~X_1, X_2, \dots, X_n~ are elements of the cycle, and if ~X_k~ is a starting point of the chain reaction, the total amount of donated money is ~f(X_1) + \dots + f(X_{k-1}) + g(X_k) + f(X_{k+1}) + \dots + f(X_n) = S - f(X_k) + g(X_k)~, where ~S~ is the sum of all ~f(X)~, and is a constant. It is clear now that we are looking for the minimum of all ~S - f(X_k) + g(X_k)~, which can easily be found by iterating through all vertices on the cycle.