City Construction

Chaewan drew up a construction plan to build bidirectional roads between buildings in a new city.

While reviewing the plan, he found that the cost was higher than expected.

Chaewan wants to cut the construction cost. He will build only the minimum set of roads so that every building is connected through roads.

The picture above is a map showing the buildings, the roads drawn as straight lines, and the cost of building each road.

Building every road in the picture costs 62. Building only the roads that connect all the buildings costs 27, so the savings are 35.

There are so many roads that Chaewan has trouble working out the savings.

Compute the savings for Chaewan.

The first line gives the number of buildings $N$ $(3 \le N \le 10^5 )$ and the number of roads $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5))$.

From the second line to the $(M + 1)$-th line, each line gives the numbers of two buildings $a$, $b$ $(1 \le a, b \le N, a ≠ b)$ and the cost $c (1 \le c \le 10^6)$ of building a road between them. No two roads connect the same pair of buildings.

Print how much of the budget can be saved. If not all buildings are connected, print -1.