Problem B
Atomically Contoured Marshmallows

You work for a company capable of producing Atomically Contoured Marshmallows. That is, marshmallows that are shaped at the atomic level to look like anything a customer desires. Due to the rampant popularity of these marshmallows, the company is looking to expand its operations by constructing more direct paths between the manufacturing plants and distributors. The factories cannot move, as the Atomically Contoured Marshmallows don’t retain their shape unless they are fabricated in alignment with certain planets and stars. Your job is to write a program that can determine the most efficient set of roads that connects all plants and distributors for a given area.

Input

Each input file consists of one test case. Each test case begins with a line $n\ c$ where $n$ represents the number of factories and distributors and $c$ represents the number of potential roads between each location. Following this, there are $c$ lines of the form $a\ b\ w$ where $a$ is the first location, $b$ is the second location, and $w$ is the cost of constructing a road between $a$ and $b$. $n$ is no more than $2\, 000$, $c$ is no more than $4\, 000$, and $w$ is no more than $50$ and greater than $0$.

Output

Output the total cost of the cheapest set of roads connecting all locations. If no set exists, output $-1$.

5 6
0 4 5
0 1 7
0 3 2
4 2 3
3 4 1
2 1 4

10

4 3
1 0 5
1 3 2
3 0 4

-1