## Ray Needs Help

View as PDF

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types

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.

#### 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.