Maximum Weight Matching in a General Graph

Time limit2sMemory limit512 MB

Summary

Given a weighted undirected graph, find a matching with maximum total edge weight.

Level: Hard9 of 10
Topics: Graph, Greedy, Dynamic programming
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples2

Example 1
Input
```
3 3
1 3 10
1 2 3
2 3 5
```
Expected output
```
10
```

Example 2

Input

Expected output