I'm looking to find the minimum perfect matchings in a weighted non-bipartite non-Euclidean complete graph, with an even number of vertices. This is, of course, for Christofides Algorithm for the Traveling Salesperson Problem.

I need to stay with a polynomial-time solution, but the number of nodes I'm working with is small enough that I really don't care if it's O(vertices^4) or O(edges * sqrt(vertices)).

Most of the information I'm finding is on the non-weighted version of the problem. A lot of what I'm finding, of course, are versions meant to shrink down the time complexity by adding extra complexity. A lot of what I'm finding is also in mathematical-type form, rather than more layman explanations or pseudocode/code. I'm looking for something a bit easier to wrap my head around, so I can of course write my own solution to the problem.

What alternatives should I be look at? Are there much simpler approximation algorithms that will get pretty close, but not perfect? Are there versions of weighted Blossom that anyone can point me to that have awful (but polynomial) time complexity, but are simpler to understand and write?

I was initially quite happy with Discrete Optimization Algorithms with Pascal Programs (Syslo, 1983/2006.) But, it's about the non-weighted version.

I've seen several places say that the weighted Blossom algorithm can be based on the non-weighted Blossom algorithm, and use it internally. Since I'm happy with the Syslo non-weighted implementation, I'd be interested if I should be considering an outer algorithm to somehow use it in the weighted case.