409049: GYM103427 H Line Graph Matching

In the mathematical discipline of graph theory, the line graph of a simple undirected weighted graph $$$G$$$ is another simple undirected weighted graph $$$L(G)$$$ that represents the adjacency between every two edges in $$$G$$$.

Precisely speaking, for an undirected weighted graph $$$G$$$ without loops or multiple edges, its line graph $$$L(G)$$$ is an undirected weighted graph such that:

• Each vertex of $$$L(G)$$$ represents an edge of $$$G$$$;
• Two vertices of $$$L(G)$$$ are adjacent if and only if their corresponding edges share a common endpoint in $$$G$$$, and the weight of such edge between this two vertices is the sum of the weights of their corresponding edges.

A maximum weighted matching in a simple undirected weighted graph is defined as a set of edges where no two edges share a common vertex and the sum of the weights of the edges in the set is maximized.

Given a simple undirected weighted connected graph $$$G$$$, your task is to find the sum of the weights of the edges in the maximum weighted matching of $$$L(G)$$$.

The first line contains two integers $$$n$$$ $$$(3 \le n \le 10^5)$$$ and $$$m$$$ $$$(n-1 \le m \le \min(\frac{n(n-1)}{2}, 2 \times 10^5))$$$, indicating the number of vertices and edges in the given graph $$$G$$$.

Then follow $$$m$$$ lines, the $$$i$$$-th of which contains three integers $$$u$$$, $$$v$$$ $$$(1 \le u, v \le n)$$$ and $$$w$$$ $$$(1 \le w \le 10^9)$$$, indicating that the $$$i$$$-th edge in the graph $$$G$$$ has a weight of $$$w$$$ and connects the $$$u$$$-th and the $$$v$$$-th vertices. It is guaranteed that the graph $$$G$$$ is connected and contains no loops and no multiple edges.

Output a line containing a single integer, indicating the sum of the weights of the edges in the maximum weighted matching of $$$L(G)$$$.

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

21

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

12

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

14