Freda的传呼机

时间限制:2s      空间限制:128MB

题目描述

为了随时与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


题目来源

Poetize9