CF2057E2 Another Exercise on Graphs (hard 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 \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 $。 确保所有测试数据的 $ q $ 总和不超过 $ 3 \cdot 10^5 $。

对于每组测试数据，输出所有查询的答案。

在第一组测试数据中，第一个查询的一个最优路径为 $ 1 \rightarrow 3 \rightarrow 4 $，这条路径上第二大的边权值为 $ 1 $。在第二个查询中，一个最优路径为 $ 2 \rightarrow 4 \rightarrow 3 $，该路径上最大的边权值为 $ 2 $。 在第二组测试数据中，第一个查询的一个最优路径为 $ 1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 6 $，这条路径上第三大的边权值为 $ 2 $。 **本翻译由 AI 自动生成**