#3732. Network

题目描述

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

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

输入格式

第一行： N, M, K。
第2..M+1行: 三个正整数：X, Y, and D (1 <= X <=N; 1 <= Y <= 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 <= N <= 15,000

1 <= M <= 30,000

1 <= d_j <= 1,000,000,000

1 <= K <= 15,000