Even though this contest is being run on April 1st, that doesn't mean we can't have legitimate algorithms problems in the set, right?

For this problem, we'll be solving the shortest path problem - given a directed graph and some weighted edges, compute the length of the shortest path between two vertices.

We would like to thank Kirito for judging this problem.

Constraints

~N = 100~

~1 \le M \le N^2 - N~

~Q = N^2~

~1 \le a, b, s, t \le N~

~1 \le w \le 10^6~

Input Specification

The first line of the input contains two nonnegative integers, ~N~ and ~M~.

The next ~M~ lines contain three space-separated integers, ~a~, ~b~, and ~w~, indicating that there is a directed edge of weight ~w~ connecting vertex ~a~ to vertex ~b~.

We guarantee that there are no parallel edges or self-loops.

The next line contains a positive integer ~Q~.

The next ~Q~ lines contain two positive integers ~s~ and ~t~, indicating a query for the length of the shortest path between ~s~ and ~t~. If there is no path between the two vertices, the answer is -1.

Output Specification

Output ~Q~ lines, the ~i~th line containing the answer for the ~i~th query.

Scoring

You will get one point per correct answer.

Note that the sample does not respect the constraints given above and is provided purely for clarity. Your solution is allowed to WA on the sample.

Sample Input

3 2
1 2 1
2 3 2
9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

Sample Output

0
1
3
-1
0
2
-1
-1
0