lectric town has only N electricity powerhouses. All these powerhouses do is generate power and transmit it to other powerhouses.

Also there are unidirectional power cables between these powerhouses. These cables go in one direction from powerhouse X to powerhouse Y.

 

Each of these cables also have a maximum integral capacity, which is an upper limit on the amount of power they can transfer. These capacities will be given.

 

Now, say a powerhouse receives R amount of power from other powerhouses, and gives out a total of S amount of power out to other powerhouses.
Further, suppose it generates G amount of power. Then the amount of power going out of the powerhouse should be the sum of the power it receives, and the power it generates. That is, S = R + G.
Since electric town is a very advanced town, G could be anything (non negative).

 

You are Jaylal, a mafia in the town, and you have a special superconducting (again unidirectional) cable. This cable has infinite capacity, and can hence transfer any amount of electricity.
You can connect this cable between from powerhouse A to powerhouse B, and since you control this cable, you will obtain the electricity that flows through this cable. You add this cable to the network, and the powerhouses continue to transmit power
in the same fashion as before, without noticing that there is another cable.

 

Of course you want to be able to get the maximum electricity. What is the maximum electricity that could be travelling in this cable?
You have to answer this question T times, for T different pairs of powerhouses A, B that you connect this cable in. All these answers have to be independently outputted. (see sample)

 

Input

 

First line of the input contains two space separated integers N and M
denoting the number of powerhouses and number of cables respectively.

 

For next M lines, each line contains three sapce separated integers U V W, denoting that there is a cable directed from powerhouse U to powerhouse V with electric capacity W.

 

A single line containing an integer T : the number of different layouts of the superconducting cable you are going to try out.
T lines follow, each containing two integers A and B denoting that the cable is connected from B to A.

 

Output

 

Output T lines each containing a single integer corresponding to the maximum electricity you can hijack in that case case.

 

Constraints

 

• 1 = N = 300
• 1 = M = N * (N - 1) / 2
• 1 = W = 10^6
• 1 = U, V = N
• 0 = G, G is unbounded from above (not given in input)
• There won’t be any duplicate edge or self loop (apart from the extra edge you added of infinite capacity)
• 1 = T = 10
• 1 = A, B = N
• A != B

 

Example

Input: 3 2 1 2 5 2 3 3 2 1 3 1 2 Output: 3 5