#3047. Freda的传呼机

题目描述

为了随时与rainbow快速交流，Freda制造了两部传呼机。Freda和rainbow所在的地方有N座房屋、M条双向光缆。每条光缆连接两座房屋，传呼机发出的信号只能沿着光缆传递，并且传呼机的信号从光缆的其中一端传递到另一端需要花费t单位时间。现在Freda要进行Q次试验，每次选取两座房屋，并想知道传呼机的信号在这两座房屋之间传递至少需要多长时间。Freda和rainbow简直弱爆了有木有T_T，请你帮帮他们吧……
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每次试验的结果。

样例

样例输入

样例输入1  

5 4 2  

1 2 1  

1 3 1  

2 4 1  

2 5 1  

3 5  

2 1  

  

样例输入2  

5 5 2  

1 2 1  

2 1 1  

1 3 1  

2 4 1  

2 5 1  

3 5  

2 1  

  

样例输入3  

9 10 2  

1 2 1  

1 4 1  

3 4 1  

2 3 1  

3 7 1  

7 8 2  

7 9 2  

1 5 3  

1 6 4  

5 6 1  

1 9  

5 7

样例输出

样例输出1  

3  

1  

  

样例输出2  

3  

1  

  

样例输出3  

5  

6

数据范围与提示

对于100%的数据，2<=N<=10000，N-1<=M<=12000，Q=10000，1<=x,y<=N，1<=t<32768