该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

N 个城市，编号为 1 ~ N。

有 M 条无向道路将所有城市连通起来，经过每条道路需要缴纳一定的费用。

现在，政府给出一项优惠政策：从城市 S 到 城市 T ，只需要缴纳路途中费用最高的那条道路所需的费用。

有 K 个人，编号为 1 ~ K。其中编号为 i 的人要从 Si 到 Ti。

每个人都想知道，如何安排行程，才能使自己缴纳的费用最少？

你能帮助他们吗？

输入

第 1 行： N, M, K。

接下来 M 行：每行三个正整数：U, V, W, 表示 U 与 V 之间有一条直接相连的道路，收费为 W。

接下来 K 行：每行两个整数 Si, Ti

输出

K 行，每行一个整数，依次表示每个人需要缴纳的最少费用。

样例输入

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

数据范围

大约 20~30% 的数据：1 ≤ N, K, M, W ≤ 20

100% 的数据： 1 ≤ N, K ≤ 15,000， 1 ≤ M ≤ 30,000， 1 ≤ U, V ≤ N， 1 ≤ W ≤ 1,000,000,000