In reading the proof of the Hungarian algorithm for the assignment problem in a weighted bigraph, I could not understand why the algorithm terminates. In the algorithm we choose a cover (namely labels for the vertices of the bigraph: $u_1\cdots u_n$, $v_1,\cdots v_n$ with $u_i+v_j\ge $weight of an edge $x_iy_j\forall i,j$) and keep adjusting it until the equality subgraph (the spanning subgraph of $K_{n,n}$ whose edges are pairs $x_iy_j$ such that $u_i+v_j=$weight of $x_iy_j$) has a perfect matching. My question is after each adjustment, why does the cost of the cover $\sum(u_i+v_i)$ reduce?
(We assume the weights are all integers).
Thanks.