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

For the $i^{th}$ query he wants to compute the minimum weight of a walk from $u_i$ to $v_i$ that takes exactly $k_i$ 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

$1\le N\le 100$

$1\le M\le N^2$

$1\le Q\le 2000$

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

$1\le u_i,v_i,a_i,b_i\le N$

$1\le w_i,k_i\le {10}^9$

Subtask 1 [25%]

$Q=1$

$k_i\le 100$

Subtask 2 [35%]

$Q=1$

Subtask 3 [40%]

No additional constraints.

Input Specification

The first line contains the integers $N$, $M$, and $Q$.

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

The next $Q$ lines each contain a query in the form $u_i,v_i,k_i$.

Output Specification

For each query $u_i,v_i,k_i$, output the shortest walk from $u_i$ to $v_i$ that uses $k_i$ 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\to 3\to 4$
• 2 4 6: $2\to 1\to 2\to 1\to 2\to 3\to 4$
• 2 4 7: It can be shown that no such walk exists.
• 2 5 3: $2\to 3\to 4\to 5$
• 3 5 1: $3\to 5$
• 3 5 2: $3\to 4\to 5$
• 3 5 3: It can be shown that no such walk exists.