题目描述

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

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

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

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

$\red {A}$：光缆不形成环，也就是光缆仅有$\red {N-1}$ 条。

$\red {B}$：光缆只形成一个环，也就是光缆仅有$\red {N }$条。

$\red {C}$：每条光缆仅在一个环中。

请你帮帮他们。

输入格式

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

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

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

输出格式

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

样例

输入样例

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

输出样例

3
1

提示

$\red {2≤N≤10000}$,

$\red {N−1≤M≤12000}$,

$\red {Q=10000}$,

$\red {1≤x,y≤N}$,

$\red {1≤t<32768}$