题目描述

给你 $n$ 个点的无向图 ($1\leq n \leq 15000$)，记为：$1 \cdots n$。图中有 $m$ 条边 ($1\leq m \leq 30000$) ，第 $j$ 条边的长度为： $d_j$ ( $1 \leq d_j \leq 10^9$). 现在有 $k$ 个询问 ($1\leq k \leq 20000$)。 每个询问的格式是： A B，表示询问从 $A$ 点走到$B$ 点的所有路径中，最长的边最小值是多少？

输入格式

第一行： $n$，$m$，$k$。 第 $2 \cdots m+1$ 行: 三个正整数：$X$，$Y$，$D$ ($1 \leq X \leq n$ $1 \leq Y \leq n$). 表示 $X$ 与 $Y$ 之间有一条长度为 $D$ 的边。 第 $m+2 \cdots m+k+1$ 行: 每行两个整数 $A$，$B$，表示询问从 $A$ 点走到 $B$ 点的所有路径中，最长的边最小值是多少？

输出格式

对每个询问，输出最长的边最小值是多少。

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

5
5
5
4
4
7
4
5

提示

$1 <= N <= 15,000$，
$1 <= M <= 30,000$，
$1 <= d_j <= 1,000,000,000$，
$1 <= K <= 15,000$。