There are N cities in a Kingdom. Since road infrastructure is not so good, some of the cities are not connected via roads. Now the King is interested in upgrading road infrastructure to such an extent that people can use roadways to travel anywhere in the Kingdom (i.e. road travel is possible between each pair of cities).Following King's initiative, minister cabinet has come up with cost matrix C (the road building cost from city i to city j, details are in input format). You need to print the minimum cost incurred to fulfill the initiative. It is always possible to make the kingdom road connected with given plan.

Note: All roads are bidirectional.

Input:
The first line contains T – the number of test cases. First line of each test case contains two integers N – the number of cities and M –the number of existing roads.
Next M lines contain city id pairs u and v (1 - based indexed) for existing roads between cities.
Next line contains a single integer K – the number of additional roads that can be built. K lines follow.
Each of these K lines consists of three space separated integers – u, v and c denoting a road between cities u and v with cost c.
1 <= T <= 10
1 <= N <= 10000
1 <= K+M <= 1000000
1 <= C <= 1000000
1 <= u, v <= N

Output:
Print the minimum cost incurred to connect cities in a way such that there exists a path between every two cities.