#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## 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 10Output

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 100Output

10

## Explanation

Build the road between provinces 2 and 3

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 15 | 10 | 1s | 32MB | Minimum |

2 | 55 | 10 | 1s | 32MB | Minimum |

3 | 30 | 10 | 1s | 32MB | Minimum |

4 | 0 | 1 | 1s | 32MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o unity -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512