题目描述

给你 $N$ 个点的无向图 ($1 \le N \le 15,000$)，记为：$1…N$。 图中有 $M$ 条边 ($1 \le M \le 30,000$)，第 $j$ 条边的长度为： $d_j$ ($1 \le d_j \le 1,000,000,000$)。

现在有 $K$ 个询问 ($1 \le K \le 20,000$)。 每个询问的格式是：$A$ $B$，表示询问从 $A$ 点走到 $B$ 点的所有路径中，最长的边最小值是多少？

输入格式

• 第一行： $N, M, K$。
• 第 $2..M+1$ 行: 三个正整数：$X, Y, and D$ ($1 \le X \le N; 1 \le Y \le N$)。 表示 $X$ 与 $Y$ 之间有一条长度为 $D$ 的边。
• 第 $M+2..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 \le N \le 15,000$
• $1 \le M \le 30,000$
• $1 \le d_j \le 1,000,000,000$
• $1 \le K \le 15,000$