Cheapest Network

Cheapest Network

A telecom company wants to connect n cities using a subset of m possible cables, cable ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​‌​​​‌‌​​‌​‌​​‌‌​‌‌​​‌‌​​​‌​​​‌‌​‌‌​​​‌‌​​​​​​‌‌​‌​‌​‌‌​​‌‌​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌‌​​‌‌​​​‌​​‌‌​‌​​​​‌‌​‌‌​​​‌‌​‌‌​i connecting cities u_i and v_i at cost w_i. Find the minimum total cost to connect all cities so that every city can reach every other city (directly or through other cities). If it's impossible to connect all cities, output -1.

Input

Line 1: ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​‌​​​‌‌​​‌​‌​​‌‌​‌‌​​‌‌​​​‌​​​‌‌​‌‌​​​‌‌​​​​​​‌‌​‌​‌​‌‌​​‌‌​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌‌​​‌‌​​​‌​​‌‌​‌​​​​‌‌​‌‌​​​‌‌​‌‌​two integers n m (1 ≤ n ≤ 2·10^5, 0 ≤ m ≤ 2·10^5) Next m lines: three integers u v w (1 ≤ u, v ≤ n, 1 ≤ w ≤ 10^9)

Output

A single integer: the minimum total cost, or -1 if the cities can't all be connected.

Example

Input:

4 5
1 2 1
2 3 2
​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​‌​​​‌‌​​‌​‌​​‌‌​‌‌​​‌‌​​​‌​​​‌‌​‌‌​​​‌‌​​​​​​‌‌​‌​‌​‌‌​​‌‌​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌‌​​‌‌​​​‌​​‌‌​‌​​​​‌‌​‌‌​​​‌‌​‌‌​3 4 3
1 3 4
2 4 5

Output:

6

Constraints

• 1 ≤ n ≤ 2·10^5, 0 ≤ m ≤ 2·10^5
• 1 ≤ w_i ≤ 10^9 ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​‌​​​‌‌​​‌​‌​​‌‌​‌‌​​‌‌​​​‌​​​‌‌​‌‌​​​‌‌​​​​​​‌‌​‌​‌​‌‌​​‌‌​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌‌​​‌‌​​​‌​​‌‌​‌​​​​‌‌​‌‌​​​‌‌​‌‌​

3 2
1 2 5
2 3 7

12

4 5
1 2 1
2 3 2
3 4 3
1 3 4
2 4 5

6