Given an integer weighted bipartite graph $$\{G,w\}$$ { G , w } 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. We construct a subgraph $$G_\mathrm{cs}$$ G cs of G, which depends on an $$\epsilon $$ ϵ -optimal solution of the dual linear program associated to the assignment problem on $$\{G,w\}$$ { G , w } , that allows us to reduce these problems to their unweighted variants on $$G_\mathrm{cs}$$ G cs . For instance, starting from scratch we get an algorithm that solves the problem of finding all the edges that occur in some minimum weight perfect matching in time $$O(\sqrt{n}m\log (nW))$$ O ( n m log ( n W ) ) , where $$n=|U|\ge |V|$$ n = | U | ≥ | V | , $$m=|E|$$ m = | E | , and $$W=\mathrm{max}\{|w(e)|\, :\, e\in E\}$$ W = max { | w ( e ) | : e ∈ E } .