题目描述

给你 $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 15,000)$。

每个询问的格式是：A B，表示询问从 $A$ 点走到 $B$ 点的所有路径中，最长的边最小值是多少？

输入格式

第一行：$N, M, K$。

第 $2..M+1$ 行：三个正整数：$X, Y, 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