CodePSU 2019 - Advanced

Start

2019-03-24 09:15 AKDT

CodePSU 2019 - Advanced

End

2019-03-24 13:15 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -671 days 4:04:57

Time elapsed

4:00:00

Time remaining

0:00:00

Problem A
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$.

Sample Input 1 Sample Output 1
5 6
0 4 5
0 1 7
0 3 2
4 2 3
3 4 1
2 1 4
10
Sample Input 2 Sample Output 2
4 3
1 0 5
1 3 2
3 0 4
-1