我们都喜欢简短直接的问题，因为它们更容易编写、阅读和理解。这里就是其中一个问题。“人生苦短，何必长篇大论”，Ahmed Aly 曾这样说道。

给定一个包含 $N$ 个节点的加权有向图（节点编号从 $1$ 到 $N$），其中边的权重各不相同且为正数。对于每个图，你还需要回答一系列查询。

每个查询由 $3$ 个整数 $A, B, C$ 表示，你需要找到从节点 $A$ 到节点 $B$ 的最短路径（即边权重之和最小的路径），该路径最多包含 $C$ 条边，且路径上边的权重必须是递增的，这意味着路径中每条边的权重都应大于其前一条边的权重（第一条边除外）。

你的任务是编写一个程序来回答这些查询。

输入格式

程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$，表示测试用例的数量（$1 \le T \le 100$）。接下来是各个测试用例，每个测试用例的第一行包含 $3$ 个由空格分隔的整数 $N, M, Q$（$2 \le N \le 150$，$0 \le M \le 3,000$，$1 \le Q \le 1,000$），分别表示节点数、边数和查询数。

随后有 $M$ 行，每行包含 $3$ 个由空格分隔的整数 $X, Y, Z$（$1 \le X, Y \le N$，$1 \le Z \le 3,000$），表示一条从节点 $X$ 到节点 $Y$、权重为 $Z$ 的边（$X$ 和 $Y$ 不同）。

随后有 $Q$ 行，每行包含 $3$ 个由空格分隔的整数 $A, B, C$（$1 \le A, B \le N$，$0 \le C \le M$），表示上述查询（$A$ 和 $B$ 不同）。

注意：同一对节点之间可能存在多条边。

输出格式

对于每个测试用例，为每个查询打印一行，包含一个整数，即满足给定约束条件下，给定节点对之间路径的最小权重和；如果不存在满足约束条件的有效路径，则输出 $-1$。输出中不得包含测试用例之间的空行。

样例

输入 1

1
8 9 3
1 2 1
2 3 2
3 4 3
4 5 12
5 8 7
1 6 8
6 4 9
1 7 5
7 4 4
1 4 2
1 4 3
1 4 1

输出 1

17
6
-1