  Given an integer weighted bipartite graph $\{G=(U\sqcup V, E), w:E\rightarrow
\mathbb{Z}\}$ we consider the problems of finding all the edges that occur in
some minimum weight matching of maximum cardinality and enumerating all the
minimum weight perfect matchings. Moreover, we construct a subgraph $G_{cs}$ of
$G$ which depends on an $\epsilon$-optimal solution of the dual linear program
associated to the assignment problem on $\{G,w\}$ that allows us to reduced
this problems to their unweighed variants on $G_{cs}$. For instance, when $G$
has a perfect matching and we have an $\epsilon$-optimal solution of the dual
linear program associated to the assignment problem on $\{G,w\}$, we solve the
problem of finding all the edges that occur in some minimum weight perfect
matching in linear time on the number of edges. Therefore, starting from
scratch we get an algorithm that solves this problem in time
$O(\sqrt{n}m\log(nW))$, where $n=|U|\geq |V|$, $m=|E|$, and $W={\rm
max}\{|w(e)|\, :\, e\in E\}$.
