Minimum Total Road Length

You are given a connected undirected graph representing towns connected by roads. Some roads already exist and you are given a list of potential new roads. Each road has a length (or weight). Your task is to determine the total length of the Minimum Spanning Tree (MST) of the graph when both the existing roads and the new potential roads are considered. In other words, you need to choose a subset of these roads such that all towns are connected and the total road length is minimized.

The problem can be mathematically stated as follows. Let \(G=(V,E)\) be a graph with \(|V|=M\). The set \(E\) contains the union of existing roads and potential new roads, each represented as a triple \((u, v, w)\) indicating a road between town \(u\) and town \(v\) with length \(w\). Find the total length of the minimum spanning tree of \(G\).

Note: The MST of a graph \(G\) is a subset of \(E\) that connects all vertices in \(V\) without any cycles and with the minimal possible total edge weight.

inputFormat

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

M R
u1 v1 w1
u2 v2 w2
... (R lines for existing roads)
K
u1' v1' w1'
u2' v2' w2'
... (K lines for new roads)

Here,

• M is the number of towns (numbered from 1 to M).
• R is the number of existing roads.
• Each of the next R lines contains three integers: u, v, and w representing a road between towns u and v with length w.
• K is the number of potential new roads.
• Each of the next K lines contains three integers in the same format representing a new potential road.

outputFormat

Output a single integer to standard output (stdout): the total length of the minimum spanning tree that connects all the towns.

## sample

4 3
1 2 5
2 3 10
3 4 3
2
1 3 2
2 4 1

6

</p>