Find a minimum-weight perfect 2-matching
From an answer to my other question it turns out that one can convert this problem to standard matching. 

Find a minimum-weight perfect b-matching, where b is even

I still wonder whether this would give the most efficient approach?