Modifying Edmonds' Blossom Algorithm
You just have to solve the following problem: Find a matching of size exactly $k$ with minimum weight. 

It can be solved by reducing to min weight perfect matching. See the paper by Ján Plesnı́k. There is a constant blow up in the number of vertices. So your original problem can be solved in $O(n^3)$ time.