题目背景

在成功修复电缆后，小鸟游六花和富樫勇太收到了一封来自WF_wxl的邀请,祂希望他们帮忙准备一道图论题，以填补比赛中的空缺。六花兴奋地认为这是展现「邪王真眼」力量的大好机会，于是即兴设计了一道关于路径上边权第 $k$ 大值的问题。

然而，题目出完后，六花和勇太却发现他们自己也不会做这道题。距离比赛开始只剩几个小时，他们急需帮助。你能代替他们解决这道难题吗？

题目描述

给定一个包含 $n$ 个顶点和 $m$ 条边的连通带权无向图，图中无自环和重边。

处理 $q$ 次形如 $(a, b, k)$ 的查询：在从顶点 $a$ 到顶点 $b$ 的所有路径中，找出路径上边权的第 $k$ 大值的最小值$^{\dagger}$。

$^{\dagger}$ 设 $w_1 \ge w_2 \ge \ldots \ge w_h$ 为某条路径中所有边权按非递增顺序排列后的结果。该路径边权的第 $k$ 大值即为 $w_k$。

输入格式

输入包含多组测试数据。第一行是一个整数 $t$（$1 \le t \le 100$），表示测试数据的组数。接下来是每组测试数据的详细描述。

每组测试数据的第一行包含三个整数 $n, m, q$（$2 \le n \le 400$，$n-1 \le m \le \frac{n(n-1)}{2}$，$1 \le q \le 3 \cdot 10^5$），分别表示图的顶点数、边数和查询数。

接下来的 $m$ 行中，每行包含三个整数 $v, u, w$（$1 \le v, u \le n$，$1 \le w \le 10^9$），表示图中的一条边及其权重。保证图中没有自环和重边。

接下来的 $q$ 行中，每行包含三个整数 $a, b, k$（$1 \le a, b \le n$，$k \ge 1$），代表一个查询。保证从顶点 $a$ 到顶点 $b$ 的所有路径至少有 $k$ 条边。

保证所有测试数据的 $n$ 总和不超过 $400$。

保证所有测试数据的 $q$ 总和不超过 $3 \cdot 10^5$。

输出格式

对于每组测试数据，输出一行，包含 $q$ 个整数，表示对应查询的答案，整数之间用空格分隔。

样例 #1

样例输入 #1

3
4 4 2
1 2 2
2 4 2
1 3 4
3 4 1
1 4 2
2 3 1
6 7 3
1 2 10
2 3 3
3 4 9
4 5 2
5 6 1
2 4 10
4 6 10
1 6 3
1 6 2
2 4 1
11 17 10
1 4 5
1 3 19
1 2 10
3 2 13
4 5 1
4 6 11
3 5 9
3 6 18
2 7 17
5 8 15
5 10 8
6 9 4
7 10 20
7 8 16
8 11 3
9 11 6
10 11 14
3 11 1
3 11 3
1 11 1
1 11 4
1 11 3
8 2 2
10 4 1
3 9 2
3 9 1
6 7 3

样例输出 #1

1 2
2 9 9
11 3 11 1 3 10 8 4 11 4

样例解释 #1

在第一组测试数据中，第一个查询的一个最优路径为 $1 \rightarrow 3 \rightarrow 4$，这条路径上第二大的边权值为 $1$。在第二个查询中，一个最优路径为 $2 \rightarrow 4 \rightarrow 3$，该路径上最大的边权值为 $2$。

在第二组测试数据中，第一个查询的一个最优路径为 $1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 6$，这条路径上第三大的边权值为 $2$。

数据范围与子任务

本题共 $20$ 个测试点，子任务划分如下：

对于 $100\%$ 的数据，满足输入格式中的全部限制。