A telecom company wants to lay cables between n hubs, numbered 0 to n - 1, so that every hub can communicate with every other hub (directly or through other hubs). There are m candidate two-way cable routes; route i connects hubs u and v at a build cost of w. Multiple candidate routes between the same pair of hubs may be offered, at different costs.

Print the minimum total cost of a set of cables that connects all n hubs into a single network. If it is impossible to connect all hubs no matter which cables are chosen, print -1 instead.

Input format

Line 1: two integers n m. Next m lines: three integers u v w -- an undirected candidate cable between hubs u and v costing w to build (hubs are 0-indexed).

Output format

A single integer: the minimum total build cost to connect all hubs, or -1 if it is impossible.

Constraints

• 1 <= n <= 1000
• 0 <= m <= 4000
• 0 <= u, v < n, u != v
• 1 <= w <= 1000

4 5
0 1 1
1 2 2
2 3 3
0 3 10
0 2 4

6

3 1
0 1 5

-1