图的询问

【题目描述】

给你N个点的无向连通图，图中有M条边，第j条边的长度为： d_j。

现在有 K个询问。

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

【输入格式】

输入文件的第一行： N, M, K。

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

【提示】

【数据规模】

对于30%的数据        1 <= N,M <= 3000，1<=K<=5000

对于50%的数据       1 <= N,M <= 3000

对于100%的数据       1 <= N <= 15,000

1 <= M <= 30,000

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

1 <= K <= 15,000

【来源】

在此键入。