CF2057E1.Another Exercise on Graphs (Easy Version)

这是该问题的简单版本。不同版本间的区别在于此版本对 $m$ 有额外约束。只有在你解决了该问题的所有版本后，才能进行 hack。

最近，"T-generation" 的导师需要筹备一场训练赛。他们发现缺少一道题目，且整场比赛中没有图论相关的问题，于是设计了如下题目。

给定一个包含 $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 \operatorname{min}(\mathbf{400}, \frac{n \cdot (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$。

保证所有测试用例的 $m$ 之和不超过 $400$。

保证所有测试用例的 $q$ 之和不超过 $3 \cdot 10^5$。

对于每个测试用例，输出所有查询的答案。

在第一个测试用例中，第一次查询的最优路径之一是 $1 \rightarrow 3 \rightarrow 4$，该路径边权的第 $2$ 大值为 $1$。第二次查询的最优路径之一是 $2 \rightarrow 4 \rightarrow 3$，边权的第 $1$ 大值为 $2$。

在第二个测试用例中，第一次查询的最优路径之一是 $1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 6$，该路径边权的第 $3$ 大值为 $2$。

翻译由 DeepSeek R1 完成