Evan is planning a new country. In his ideal country, there are ~N~ cities connected by ~M~ weighted directed roads. The weight of each road is the distance between the two cities it is connecting. These cities are grouped into ~P~ provinces. A province, according to Evan, is a maximal group of cities such that every city is able to visit every other city in that province.

Evan wants to keep the provinces as segregated as possible for reasons we dare not know about. As such, he has decided that there will only be ~P-1~ roads connecting the ~P~ provinces. These ~P-1~ roads are included in the initial ~M~ roads. Furthermore, he has guaranteed that all provinces are connected, that is, each province has either an indegree greater than ~0~, an outdegree greater than ~0~, or both. In other words, the provinces form a tree.

Soon after, Evan is told that with his current plan, not every province can visit every other province. Realizing his mistake, he has decided that all roads between any two provinces will be upgraded to be bidirectional. The distance between city ~a~ and city ~b~ in both directions, however, will be the same.

With the country's roads planned out, Evan wants you to find the distance between two cities so that he can decide if any other roads needs to be built. He will ask you ~Q~ times.

Input Specification

The first line will contain three space-separated integers, ~N~ ~(1 \le N \le 10^4)~, ~M~ ~(1 \le M \le 10^5)~, ~Q~ ~(1 \le Q \le 10^5)~, the number of cities, roads, and queries respectively.

The next ~M~ lines will each contain three space-separated integers, ~a_i~ ~b_i~ ~d_i~ ~(1 \le a_i,b_i \le N,a_i \neq b_i, 1 \le d_i \le 10^5)~ indicating that there is a road connecting city ~a_i~ and city ~b_i~ of length ~d_i~.

The next ~Q~ lines will each contain two space-separated integers, ~a_i~ ~b_i~ ~(1 \le a_i, b_i \le N, a_i \neq b_i)~, indicating that Evan would like to know the distance from city ~a_i~ to city ~b_i~.

It is guaranteed that ~1 \le P \le 10^3~, and ~p_i \le 200~. That is, the number of provinces is less than or equal to ~10^3~ and the number of cities in each province is less than or equal to ~200~.

Subtasks

For 2 of the 25 available marks, ~Q \le 100~.

For an additional 4 of the 25 available marks, ~p_i = 1~.

For an additional 4 of the 25 available marks, ~d_i = 1~.

Output Specification

For each query, output the minimum distance from ~a_i~ to ~b_i~ on a new line for Evan.

Sample Input 1

10 13 5
1 2 3
2 3 2
3 1 10
4 1 5
3 4 7
10 3 2
6 10 1
6 7 8
5 7 7
5 6 4
7 8 6
8 9 9
9 5 1
1 8
3 1
9 10
5 2
4 6

Sample Output 1

22
10
6
20
13

Sample Input 2

9 12 4
1 2 1
2 1 1
1 3 1
3 4 1
4 3 1
2 5 1
5 6 1
6 5 1
6 7 1
6 8 1
8 9 1
9 8 1
1 9
7 4
2 8
6 3

Sample Output 2

5
6
3
4

Sample Input 3

14 19 7
1 2 1
2 3 5
3 1 3
2 4 2
4 5 4
5 4 1
4 10 8
10 11 10
11 12 5
12 11 6
4 6 3
6 7 1
7 8 3
8 9 2
9 6 1
8 6 4
7 13 2
13 14 5
14 13 1
1 8
13 12
5 9
11 3
7 4
2 14
10 6

Sample Output 3

10
34
10
25
9
13
11