You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

最近的事情真的是太多了，导致我们亲爱的小Y每天都要坐1e5次高铁？？？？？

C国中有n个城市，其中有m条直接相连的高铁道路，走每条道路需要的花费为wi。如果A点到B点有直接相连或间接相连的高铁道路，那么这两个点是互相可达的。

对于这样的优质客户，铁路部门推出了一种全新的计费模式。假设小Y要按照一条路线从A点到B点，原本的费用是这条路线上每条直接相连的高铁道路的费用和，现在他只需要付这条道路上直接相连的高铁道路的费用的最大值。

由于他每天要坐$100000$次高铁，所以他想问你，每次从A点到B点，最少需要付多少钱？如果你无法找到一条合理的路线，也请你告诉他。

题目描述

给定一个n个点，m条边的带权无向图，你需要完成q个询问。

对于每次询问，你需要找到一条从A到B的路径，使这条路径中边权的最大值最小。（因为从A到B不一定只有一条路径！！！）如果你找不到这样的一条路径，请输出-1，否则输出需要的花费。

输入格式

第一行，输入n，m，q。分别表示图的点数，图的边数，你需要处理的询问数。

接下来m行，每行三个数字，u，v，w，表示u和v由一条边权为w的边相连。（数据保证没有重边，即不会存在u和v由两条及以上的边相连！）

接下来q行，每行两个数字，u，v，表示小Y需要从u点到v点。

输出格式

你一共需要输出q行，每行一个数字，表示从$u_i$到$v_i$的最小花费是多少。

5 7 3
1 3 1
1 4 3
1 5 5
2 3 5
3 4 5
3 5 4
4 5 1
1 3
2 4
1 5

1
5
3

说明/提示

样例解释：

对于最后一个询问，我们有四种路径：

1->5 w=5

1->4->5 w=3

1->4->3->5 w=5

1->3->5 w=4

所以最小值为3。

数据范围：

数据保证$1 \le w \le 10^6$

特殊性质为，保证图中无环。