Maximum Weighted Matching

Given an undirected weighted graph with \(n\) vertices and \(m\) weighted edges, find a matching (a set of edges that do not share any vertex) such that the total weight of the selected edges is maximized. Not all vertices need to be matched, and the graph is not necessarily bipartite.

Formula: \(\max \sum_{e \in M} w_e\)

inputFormat

The first line contains two integers n and m representing the number of vertices and edges respectively.
Each of the next m lines contains three integers: u, v, and w, indicating that there is an edge between vertices u and v with weight w. Vertices are numbered from 1 to n.

outputFormat

Output a single integer representing the maximum achievable total weight of a matching.

sample

4 4
1 2 3
1 3 5
2 4 6
3 4 4

11