Minimum Cost to Construct a Road Network

The Kingdom of Codesland comprises (N) cities connected by some existing bidirectional roads. The king wishes to extend the road network by building new roads so that the final network forms a tree. In other words, there must be exactly one unique path between any two cities.

Given the list of existing roads and a list of potential new roads, your task is to compute the minimum total cost required to construct such a network. If it is impossible to connect all cities in this way, output (-1).

inputFormat

Input is read from standard input (stdin) and has the following format:

(N) (M)
Next (M) lines: each line contains three integers (u), (v), and (w) representing an existing road between cities (u) and (v) with cost (w).
Next line: (K)
Next (K) lines: each line contains three integers (u), (v), and (w) representing a potential new road with cost (w).

outputFormat

Output a single integer to standard output (stdout): the minimum total cost to construct a tree that connects all (N) cities. If it is impossible, output (-1).## sample

4 3
1 2 3
2 3 1
3 4 4
2
1 4 2
2 4 3

6