题目描述

为了随时与 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 每次试验的结果。

样例

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

3
1

数据范围

$2≤N≤10000, N−1≤M≤12000, Q=10000, 1≤x,y≤N,1≤t<32768$

来源

• 算法竞赛进阶指南