Cheap Flights

Time limit2sMemory limit1024 MB

Summary

Given a weighted graph, pick a set of edges with pairwise nonempty intersection maximizing total weight.

Level: Hard8 of 10
Topics: Graph, Greedy, Brute force, Combinatorics
Solved: No attempts yet

Problem

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$ cities most popular among tourists and worked out which routes between these cities would be profitable. Each route connects two cities, and its profitability is the number of Euros per month that Justas Airlines would earn by operating it.

The routes must be chosen so that every two chosen routes share a common city. Compute the maximum profit that Justas Airlines can make in one month.

Input

The first line contains the number of cities $N$ and the number of profitable routes $M$ . The cities are labeled from $1$ to $N$ .

Each of the next $M$ lines contains three integers $a_i$ , $b_i$ , and $p_i$ : $a_i$ and $b_i$ are the two cities joined by the $i$ -th route, and $p_i$ is its profitability. No two routes connect the same pair of cities.

Output

Output a single integer: the maximum possible profit.

Constraints

$1 \le N \le 300000$
$1 \le M \le 500000$
$1 \le a_i, b_i \le N$
$1 \le p_i \le 1000000000$

Examples3

Example 1
Input
```
5 4
1 2 1
1 3 2
1 4 1
2 4 1
```
Expected output
```
4
```

Example 2

Input

Expected output

Example 3

Input

Expected output