Chocolate Delivery

Farmer John is distributing chocolates at the barn for Valentine’s Day. He has B bulls, each with a special cow in mind. The farm consists of N pastures (numbered from 1 to N), connected by M bidirectional cowpaths, each with a positive length. The barn is located in pasture 1. For each bull, given his current pasture P and his target cow’s pasture Q, the goal is to compute the sum of the shortest distance from P to the barn and then from the barn to Q.

More formally, let \(d(u,v)\) denote the shortest distance between pastures \(u\) and \(v\). For every bull with starting pasture \(P_i\) and target pasture \(Q_i\), output \(d(P_i,1)+d(1,Q_i)\).

The input satisfies the following constraints:

• \(1 \le B \le 25000\)
• \(2B \le N \le 50000\)
• \(N-1 \le M \le 100000\)
• For each cowpath \(i\): \(1 \le R_i, S_i \le N\) and \(1 \le L_i \le 2000\)
• Each bull is specified by two integers \(P_i\) and \(Q_i\) satisfying \(1 \le P_i, Q_i \le N\).

You can assume that the barn (pasture 1) is reachable from every other pasture.

inputFormat

The input begins with a line containing three integers: N (number of pastures), M (number of cowpaths), and B (number of bulls).

Then follow M lines, each containing three integers Ri Si Li describing a bidirectional cowpath between pastures Ri and Si with length Li.

After that, there are B lines. The i-th such line contains two integers Pi and Qi indicating that bull i is at pasture Pi and wishes to deliver a chocolate to the cow located in pasture Qi.

outputFormat

For each bull, output a single line with one integer: the sum of the shortest distance from the bull's pasture to the barn (pasture 1) and from the barn to his target cow's pasture.

sample

6 6 3
1 2 3
1 4 3
1 3 1
5 4 3
4 3 2
1 6 9
2 4
3 6
5 1

6
10
6