A campus has n buildings, numbered 0 to n - 1. Some pairs of buildings already have a
free, existing network trunk between them (m1 such pairs). In addition, there are m2 candidate
priced links that could be built; candidate link i connects buildings u and v at a cost of w.
Choose a subset of the candidate links (in addition to all of the free existing trunks) so that every
building ends up connected to every other building, directly or indirectly. Print the minimum total
cost of the candidate links you must buy to achieve this. If it is impossible to connect all buildings
even using every candidate link, print -1 instead.
Input format
Line 1: three integers n m1 m2.
Next m1 lines: two integers u v -- an existing free trunk between buildings u and v.
Next m2 lines: three integers -- a candidate link between buildings and costing
to build.
All buildings are 0-indexed; all links are undirected.
Output format
A single integer: the minimum total cost of candidate links needed to connect every building, or -1
if it cannot be done.
Constraints
- 1 <= n <= 1000
- 0 <= m1, m2 <= 2000
- 0 <= u, v < n, u != v
- 1 <= w <= 1000