Maximum Weight Matching in a General Graph

You are given a weighted undirected graph with $N$ vertices and $M$ edges. Write a program that prints the total weight of a maximum weight matching of that graph.

In a graph $G = (V, E)$, a matching $T$ is a subset of $E$ in which no two edges share a vertex. A maximum weight matching is a matching whose edge weights add up to the largest total. The empty set, which takes no edge at all, is also a matching.

The first line contains the number of vertices $N$ ($1 \le N \le 400$) and the number of edges $M$ ($1 \le M \le N(N-1)/2$).

Each of the next $M$ lines holds the information of one edge: the numbers of the two distinct vertices it joins, and its weight.

A vertex number is a natural number between 1 and $N$, and an edge weight is a natural number between 1 and 500,000,000. There is at most one edge between any two vertices.

Print the total weight of a maximum weight matching on the first line.