描述

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

样例输出1

3
1

样例输入2

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

样例输出2

3
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

样例输出3

5
6

数据范围与约定

• 颂芬数据占10%，2<=N<=1000，N-1<=M<=1200。
  A 类数据占30%，M=N-1。
  B 类数据占50%，M=N。
  C 类数据占10%，M>N。
  对于100%的数据，2<=N<=10000，N-1<=M<=12000，Q=10000，1<=x,y<=N，1<=t<32768。

来源

石家庄二中【Nescafé 26】杯NOIP模拟赛