Cartman is a very lazy kid. He wants to minimize his walking as much as he can. He has the list of all the cities in south park and also the list of all the roads in there. Every road is identified by the pair of cities it connects and its length. Now Cartman asked you what is the shortest distance to go from city "A" to city "B", please help him. If there are "N" cities in south park, they will be numbered as 0, 1, 2 ... N-1.

Input

The first line will contain two integers "N" the number of cities and "R" the number of roads connecting them. Each of the next "R" lines has three integers "X Y L" which means that city "X" and city "Y" are connected by a road of length "L". The next line contains an integer "Q", the number of queries asked by Cartman. Each of the next "Q" lines contains two integers "A B" denoting a pair of cities queried by Cartman.

Output

For each query "Q" you have to tell him the lenght of the shortest path to reach from "A" to "B" in a different line. It is guaranteed that there will be a path from every city to every other city.

Constraints

1 <= N <= 100

1 <= R <= N * (N - 1) / 2

0 <= X, Y <= N - 1

1 <= L <= 1000

1 <= Q <= 1000

0 <= A, B <= N - 1

Example

Input:
5 5
0 1 1
0 4 2
4 3 2
1 3 2
3 2 3
4
0 1
3 0
2 0
4 2

Output:
1
3
6
5