为了随时与rainbow快速交流，Freda制造了两部传呼机。Freda和rainbow所在的地方有N座房屋、M 条双向光缆。

每条光缆连接两座房屋，传呼机发出的信号只能沿着光缆传递，并且传呼机的信号从光缆的其中一端传递到另一端需要花费t单位时间。

现在Freda要进行Q次试验，每次选取两座房屋，并想知道传呼机的信号在这两座房屋之间传递至少需要多长时间。

N座房屋通过光缆一定是连通的，并且这M条光缆有以下三类连接情况：

A：光缆不形成环，也就是光缆仅有N-1 条。
B：光缆只形成一个环，也就是光缆仅有N 条。
C：每条光缆仅在一个环中。

请你帮帮他们。

输入格式

第一行包含三个用空格隔开的整数，N、M 和Q。

接下来M行每行三个整数x、y、t，表示房屋x和y之间有一条传递时间为 t 的光缆。

最后Q行每行两个整数x、y，表示Freda想知道在x和y之间传呼最少需要多长时间。

输出格式

输出Q行，每行一个整数，表示Freda每次试验的结果。

数据范围

$2 \le N \le 10000$,
$N-1 \le M \le 12000$,
$Q = 10000$,
$1 \le x,y \le N$,
$1 \le t < 32768$

输入样例：

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

输出样例：

3
1

来源

• 《算法竞赛进阶指南》
• acwing 可能含有视频讲解