Network Connection

Dohyun wants to connect all N computers into one network. Because there is no hub, he must choose direct connections between pairs of computers.

Two computers are considered connected if there is a direct connection between them or a path through one or more other computers.

Each possible connection has an installation cost. Find the minimum total cost needed to choose connections so that every computer belongs to one connected network. Every given input can connect all computers.

The first line contains the number of computers N (1 ≤ N ≤ 1000).

The second line contains the number of possible connections M (1 ≤ M ≤ 100,000).

Each of the next M lines contains three integers a, b, and c. This means that directly connecting computer a and computer b costs c (1 ≤ c ≤ 10,000). The values a and b may be the same.

Print the minimum total cost required to connect all computers into one network.

In the public sample, choosing connections 1-3, 2-3, 3-4, 4-5, and 4-6 gives the minimum cost 23.