Chocolate Giving

The farmer is handing out chocolates at the barn for Valentine's Day. $B$ ($1 \le B \le 25000$) bulls each have a special cow in mind to receive a chocolate gift.

Each bull and cow grazes alone in one of the farm's $N$ ($2B \le N \le 50000$) pastures, numbered $1$ through $N$ and connected by $M$ ($N-1 \le M \le 100000$) bidirectional cowpaths of various lengths. Two pastures may be directly connected by more than one cowpath. Cowpath $i$ connects pastures $R_i$ and $S_i$ ($1 \le R_i \le N$; $1 \le S_i \le N$) and has length $L_i$ ($1 \le L_i \le 2000$).

Bull $i$ lives in pasture $P_i$ ($1 \le P_i \le N$) and wants to give a chocolate to the cow in pasture $Q_i$ ($1 \le Q_i \le N$).

Help each bull find the shortest route from its own pasture to the barn (located at pasture $1$) and then onward to the pasture where its special cow grazes. The barn is connected -- directly or indirectly -- to every pasture.

For example, consider a farm with 6 pastures, 7 cowpaths, and 3 bulls (in pastures 2, 3, and 5) who each want to deliver a chocolate:

                     *1  <-- this bull wants to gift the cow in pasture 1
             [4]--3--[5]  <-- [5] is the pasture ID
            /  |
           /   |
          4    2          <-- 2 is the length of the cowpath
         /     |               between [3] and [4]
      [1]--1--[3]*6
     /   \    /
    9     3  2
   /       \/
 [6]      [2]*4

The bull in pasture 2 can travel distance 3 to reach the barn, then distance 2 + 1 to pastures 3 and 4, for a total of 6.

The bull in pasture 5 can travel to pasture 4 (distance 3), then on to pastures 3 and 1 (3 + 2 + 1 = 6).

The bull in pasture 3 can travel distance 1 to pasture 1, then carry the chocolate 9 more to pasture 6, for a total distance of 10.

• Line 1: three space-separated integers $N$, $M$, and $B$.
• Lines 2 to $M+1$: line $i+1$ describes cowpath $i$ with three space-separated integers $R_i$, $S_i$, and $L_i$.
• Lines $M+2$ to $M+B+1$: line $M+i+1$ contains two space-separated integers $P_i$ and $Q_i$.

• Lines 1 to $B$: line $i$ contains a single integer, the smallest total distance the bull in pasture $P_i$ must travel to pick up a chocolate at the barn and then deliver it to the cow of his dreams in pasture $Q_i$.