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

Precisely speaking, for an undirected weighted graph without loops or multiple edges, its line graph is an undirected weighted graph such that:
Each vertex of represents an edge of ;
Two vertices of are adjacent if and only if their corresponding edges share a common endpoint in , 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 , your task is to find the sum of the weights of the edges in the maximum weighted matching of .

The first line contains two integers   and  , indicating the number of vertices and edges in the given graph .

Then follow  lines, the -th of which contains three integers ,   and  , indicating that the -th edge in the graph  has a weight of  and connects the -th and the -th vertices. It is guaranteed that the graph  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 .

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