Ray is planning something and needs your help. Ray needs your help to answer queries on a directed, weighted graph of nodes and edges.

For the query he wants to compute the minimum weight of a walk from to that takes exactly edges, and if no such walk exists, output `-1`

instead. A walk is similar to a path, but edges (and nodes) can be traversed multiple times. The weight of a walk is equal to the sum of weights of the edges it traverses, and if an edge is traversed multiple times, its weight will count multiple times towards the sum.

#### Constraints

**There may be duplicate edges and/or self-loops.**

##### Subtask 1 [25%]

##### Subtask 2 [35%]

##### Subtask 3 [40%]

No additional constraints.

#### Input Specification

The first line contains the integers , , and .

The next lines each contain the integers , meaning that there is a directed edge from to with a weight of . Note that it may be possible for a single pair of nodes to have multiple edges between them.

The next lines each contain a query in the form .

#### Output Specification

For each query , output the shortest walk from to that uses edges. If no such walk exists, output `-1`

instead. The output of each query should be on a separate line.

#### Sample Input

```
5 7 7
2 1 1
1 2 3
1 4 10
4 5 1
3 4 1
2 3 4
3 5 5
2 4 2
2 4 6
2 4 7
2 5 3
3 5 1
3 5 2
3 5 3
```

#### Sample Output

```
5
13
-1
6
5
2
-1
```

#### Sample Explanation

Here are the answers to each query:

`2 4 2`

:`2 4 6`

:`2 4 7`

: It can be shown that no such walk exists.`2 5 3`

:`3 5 1`

:`3 5 2`

:`3 5 3`

: It can be shown that no such walk exists.

## Comments