Tourist Huseyn#10202
Huseyn decided to travel to another country, but during the coronavirus season it is difficult to find a cheap route. The bus driver has a list of cities in his country and has calculated which routes between these cities would bring the greatest profit. Each route connects two cities. The cost of a route is the amount the driver would earn by choosing this route.
It is required to select a set of routes such that any two of them share a common city. Calculate the maximum possible profit the bus driver can obtain.
The first line contains two integers: the number of cities n~(1 \le n \le 3 \cdot 10^5) and the number of routes m~(1 \le m \le 5 \cdot 10^5). The cities are numbered from to .
Each of the next lines contains three integers: a_i, b_i~(1 \le a_i, b_i \le n) and p_i~(1 \le p_i \le 10^9 for all , where a_i and b_i are the cities connected by the -th route, and p_i is its cost. It is guaranteed that no two routes connect the same pair of cities.
Print a single integer — the maximum possible profit.
Example
4 5
1 2 1
1 3 2
1 4 1
2 4 1
3 4 14Explanation for the first example:
Choosing the routes 1 - 2, 1 - 3, 1 - 4 gives a total cost of , which is the correct answer. You could also choose the routes 1 - 2, 1 - 4, 2 - 4, but in this case the total cost would be smaller — .