Minimum Road Trip Cost

You are given a network of N cities. Some roads between the cities are already built and have associated travel costs, while some additional potential roads can be constructed at a given construction cost. Starting from city 1, your goal is to ensure that all cities are connected (i.e. it is possible to travel between any pair of cities). Effectively, you are to choose a subset of roads (both existing and potential) such that the total cost is minimized and all cities are connected. If it is not possible to connect all cities, output -1.

You can model the problem as a minimum spanning tree (MST) problem. In mathematical terms, given a graph \(G=(V,E)\) where \(|V| = N\), you are to choose a subset \(T \subseteq E\) such that \(T\) connects all vertices and the total cost, defined as \(\sum_{e \in T}cost(e)\), is minimized. If such a tree does not exist, print -1.

Note: The input is given via standard input (stdin) and the output must be printed to standard output (stdout).

inputFormat

The first line contains two integers \(N\) and \(M\), where \(N\) is the number of cities and \(M\) is the number of existing roads.

The next \(M\) lines each contain three integers \(u\), \(v\), and \(w\), which denote that there is an existing road connecting city \(u\) and city \(v\) with cost \(w\).

The following line contains an integer \(K\), the number of potential roads.

The next \(K\) lines each contain three integers \(u\), \(v\), and \(w\), indicating that a potential road between city \(u\) and city \(v\) can be constructed at a cost \(w\).

All input values are provided via stdin.

outputFormat

Output a single integer representing the minimum total cost to ensure all cities are connected. If it is impossible to connect all cities, output -1.

The output should be printed to stdout.

## sample

4 2
1 2 500
3 4 600
2
1 3 200
4 2 300

1000