「BZOJ2125」最短路

Description

给一个NN个点MM条边的连通无向图,满足每条边最多属于一个环,有QQ组询问,每次询问两点之间的最短路径。

Input

输入的第一行包含三个整数,分别表示NNMMQQ
下接MM行,每行三个整数vvuuww表示一条无向边vuv-u,长度为ww
最后QQ行,每行两个整数vvuu表示一组询问

Output

输出QQ行,每行一个整数表示询问的答案

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
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

Sample Output

1
2
5
6

HINT

对于100%100\%的数据,N10000N\leq 10000Q10000Q\leq 10000

Solution