7260번 - Cheap flights 서브태스크다국어

Justas built a passenger airplane, and now he wants to start a low cost airline, called Justas Airlines.

Justas made a list of the N most popular cities among tourists, and calculated which routes between these cities would be profitable. Each route connects two cities. The profitability of the route indicates how many Euros per month Justas Airlines would earn by operating the route.

Routes have to be chosen so that any two routes have one city in common. Calculate the maximum profit that Justas Airlines can make in one month.

The first line shows the number of cities N, and the number of profitable routes M. Cities are labeled 1 to N. The following M lines contain three numbers each – a_i, b_i, and p_i, where a_i and b_i are the two cities joined by the i-th routes, and p_i is the profitability of the route. No two routes connect the same pair of cities.

Output a single number: the maximum possible profit.

• 1 ≤ N ≤ 300 000
• 1 ≤ M ≤ 500 000
• 1 ≤ a_i, b_i ≤ N
• 1 ≤ p_i ≤ 1 000 000 000