Ants (Challenge)

You are given a directed weighted graph with $N$ vertices (numbered $1$ through $N$) and $M$ edges (numbered $1$ through $M$). For each valid $i$, the $i$-th edge is initially directed from a vertex $u_i$ to a vertex $v_i$ and it has a *flipping cost* $W_i$. There is one ant living in each vertex of the graph. Let's denote a directed edge from a vertex $u$ to a vertex $v$ by $(u, v)$. The outdegr