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

for judging this problem.#### Constraints

#### Input Specification

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

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

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

The next line contains a positive integer .

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

.

#### Output Specification

Output lines, the th line containing the answer for the 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
```

## Comments