Problem Description
One man united the warring states
One man dominated all his enemies
That one man is you
And he has realised what a fragmented mass the kingdoms are after the war
The different provinces of the kingdom are connected by bi-directional roads. After the war, many roads have fallen into disrepair, but some still can be used
You can build a some roads between 2 kingdoms, but it will cost you a certain amount of resources.
In order to unite the kingdoms, you will need to connect all the provinces together such that one can move to every other province from any single province using a series of roads [Hint Hint, what is this type of problem?]
However, as you have just ended a war, the opportunity cost of building roads is very high, hence you want to minimise the amount of resources required to do so
Input
The first line of the input contains one integer, the number of provinces n [Provinces are 1 based, i.e. there exist province 1 to n]
The next line contains one integer, the number of working roads, w
The next w lines each contain a pair of integers, wa and wb, where a bidirectional road joins provinces wa and wb
The next line contains one integer, the number of buildable roads, b
The next b lines each contain 3 integers, ba, bb and bc, where a bidirectional road could connect ba to bb at the cost of bc
There will never be more than 1 buildable or working road between 2 distinct provinces
Constraints
n<=10,000, w<=100,000, b<=1,000,000
Output
Output the minimum amount of resources needed to build a road network
If it is impossible to build a road network, output -1
Subtasks
Subtask 1 (15%) w=0, b=n-1, it is guaranteed that it will be possible to build a network
Subtask 2 (55%) w=0, all other above constraints apply
Subtask 3 (30%) Above constraints apply
Sample Testcase 1
Input
3
2
1 2
2 3
1
1 3 10
Output
0
Explanation
You don't need to build anything
Sample Testcase 2
Input
4
2
1 2
2 4
2
2 3 10
1 4 100
Output
10
Explanation
Build the road between provinces 2 and 3