Nick is the mayor of JosephLand. He wants to make a reform of the roads in JosephLand. In JosephLand, there are n cities, numbered 1 through n. There are also m weighted, directed roads represented by three numbers:
Nick is going to have a travel. Travel consists of q journeys. Each journey is represented by two numbers: ai,bi. That means, he starts his journey in ai and ends in bi. Every time he will choose a journey with minimum cost. Cost of a journey is equal to the sum of fines he paid during the journey.
Consumption of a travel is ∑qj=1costj. As Nick is the mayor of JosephLand, before the travel he can change directions of any roads as many times as he wants. So now Nick wants to change directions of some roads in such a way, that consumption is minimal. Note that no changes can be made.
Input format
The first line contains two integers n, m — the number of cities and the number of roads, respectively.
Next m lines contain three integers each, ui, vi and wi denoting there is a road from ui to vi and the fine is wi. Note that between a pair of cities can exist more than one road.
Next line contains a single integer q — the number of journeys.
Next q lines contain two integers each, ai and bi — the start and the end of the journey, respectively. Note that the start and the end can be the same city.
It is guaranteed that the JosephLand is connected.
Note: there can be a problem with stack size.
Output format
Print the minimum consumption that Nick can achieve.
Constraints
Subtasks
We can change directions of first and third roads. The graph will be as follows:
From 6 to 5 there is only path and we don't pay anything, so cost1 = 0
From 7 to 5 we have to pay fine for passing the road from 5 to 4, so cost2 = 10
Overall consumption =10 and you can not achieve better than this answer!