Rules and regulations about mileage reimbursement for employees are very clear: the employee should be refunded an amount of money proportional to the shortest distance between their home and office. This causes your X-mas Ornaments Retailer a great deal of pain: every year more and more money is spent on reimbursement and this means your companies have less profit! This obviously has to be stopped and so you delve deep into the regulations about reimbursement, hoping to find a loophole so you do not have to give as much money to your employees. 

    However, the rules seem pretty strict. As long as the employees keep track of the distances they have travelled, you are forced to reimburse them. Suddenly you have a flash of inspiration: nowhere does it say that you have to use the  distances! You start working on more subtle distance functions and now you have a first prototype:  distance. The length of a path is defined as the  of the lengths of the edges on the path (as opposed to the sum). The distance between two locations is defined as the length of the shortest path between them. You hope that the authorities will not notice that this does not define a metric, but before you send them your proposal you want to experiment with this distance first.

    You cook up a simple connected weighted undirected graph with this distance function, and you ask yourself  questions about this graph, each asking about the shortest  distance between two nodes.

The input consists of:
One line containing three integers  (), (), and  (), the number of nodes, edges, and questions respectively.
 lines describing an edge. Each line consists of three integers , ,  (,  and ), indicating that there is an undirected edge of length  between nodes  and .
 lines describing a question. Each line consists of two integers ,  () asking for the shortest distance between nodes  and .

For every question, output one line containing the shortest distance between nodes  and .

3 3 3
1 2 2
1 3 2
2 3 3
1 2
1 3
2 3

1
1
0

7 10 5
1 2 45
2 3 11
2 4 46
3 4 28
3 5 59
3 6 12
3 7 3
4 5 11
5 6 23
6 7 20
1 4
2 6
3 5
1 7
5 5

1
5
0
5
0