U201076 [Bzoj3732] Network

题目描述

给定一张 $N$ 个点的无向图，记为 $1\cdots N$ 。

图中有 $M$ 条边，第 $j$ 条边的长度为 $d_j$ 。

现在有 $K$ 个询问，每个询问的格式为 $A\ \ B$，表示询问从 $A$ 走到 $B$ 的所有路径中，最长边的最小值为多少。

输入格式

第一行为三个整数 $N, M, K$ 。

第二行到第 $M+1$ 行，每行三个整数 $X, Y, D$ ，表示从 $X$ 与 $Y$ 之间有一条长度为 $D$ 的边。

第 $M+2$ 行到第 $M+K+1$ 行，每行两个整数 $A, B$ ，意义如上。

输出格式

共 $K$ 行。

对于每个询问，输出最长边的最小值。

输入输出样例 #1

输入 #1

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

输出 #1

5
5
5
4
4
7
4
5

说明/提示

$1 \leq N \leq 15000$

$1 \leq M \leq 30000$

$1 \leq D_j \leq 10^9$

$1 \leq K \leq 15000$