Problem F
Frugal Ferry Fees

Here at Mercury Merchants, we do not only sell grain, leather and high-quality wood, we also deliver it straight to our customer’s door! And if we don’t have it in stock, we simply send it by horse and cart from the nearest town.

Of course, getting the goods delivered over water is an entirely different matter, as we don’t own any ships ourselves. In order to save costs for ferry fees, we happily formed an agreement with Charon Corporation some time ago. The prices we get for ferry trips are amazing, although our couriers are a bit creeped out by the ferrymen: They are all slender, tall men in black hoods, and all of them are named Charon. Oh well – some sleepless nights are warranted in the pursuit of profit and increased margins.

Figure 1: Map over Sample Input 1

However, Charon Corporation has had to raise their prices quite significantly since the black plague due to “abnormal demand for other services we provide”, according to their sales representative (also named Charon). While the prices are still much better than Charon Corporation’s competitors, our bottom line will turn red if we don’t optimise the ferry fees.

The solution to our problems is quite simple: While our couriers in the past took the shortest path from A to B, we’ll now order them to take the route which minimises ferry costs instead.

Input

The first line contains two integers, $V$ and $E$, the number of cities and the number of cart routes between them. Then follow $E$ lines, describing the cart routes. Each line contains two integers $town1_ i$ and $town2_ i$, describing an undirected cart route between the two towns.

Next follows a single line containing an integer $F$, representing the number of ferry lines Charon Corporation has set up. $F$ lines follow, all with three integers each: $town1_ i$, $town2_ i$ and $cost_ i$, where the two first integers denote the towns the ferry go via, and $cost_ i$, which is the number of oblates you have to pay to Charon Corporation for the trip.

Finally a line with an integer $Q$ follows, representing the number of trips you have to perform. $Q$ lines follow, and each contains two integers $town1_ i$ and $town2_ i$, describing that you have to travel from town $1$ to town $2$.

As the input may be very large, you should consider buffering it.

Output

Output the minimum number of oblates needed to perform all travels.

Limits

• $1 < V < 200\, 000$, $0 \leq E < 500\, 000$

• $0 < F < 300$

• $0 < Q < 500\, 000$

• $0 \leq town1_ i, town2_ i < V$, $town1_ i \neq town2_ i$

• $0 < cost_ i < 1\, 000$

• There exists at least one path from any town to any other town.

12 12
0 2
0 3
2 3
3 4
3 5
6 7
6 8
6 10
7 8
7 10
8 9
8 10
6
0 1 7
0 10 5
1 2 4
5 6 1
5 11 9
9 11 2
7
1 11
5 8
4 1
4 10
9 11
2 4
3 8

16