En San Valentín Farmer John reparte chocolate en el establo. $B$ toros ($1 \le B \le 25,000$) quieren regalarlo a una vaca especial.

Cada toro y vaca pasta solo en uno de $N$ pastos ($2B \le N \le 50,000$), numerados $1..N$, unidos por $M$ caminos bidireccionales ($N-1 \le M \le 100,000$) de distintas longitudes. Puede haber varios entre una pareja. Camino $i$ une $R_i$, $S_i$ ($1 \le R_i \le N; 1 \le S_i \le N$), longitud $L_i$ ($1 \le L_i \le 2,000$).

Toro $i$ está en $P_i$ ($1 \le P_i \le N$), regala a la vaca en $Q_i$ ($1 \le Q_i \le N$).

Halla la ruta mínima al establo (1) y luego a la vaca. El establo conecta con todos a través de caminos y pastos.

Ejemplo con 6 pastos, 6 caminos, 3 toros en 2, 3, 5 para sus amadas:

                      *1  <-- Toro quiere chocolate para vaca del pasto 1
             [4]--3--[5]  <-- [5] es el número del pasto
            /  |
           /   |
          4    2          <-- 2 es la longitud del camino
         /     |               entre [3] y [4]
      [1]--1--[3]*6
     /   \    /
    9     3  2
   /       \/
 [6]      [2]*4

• El de 2 recorre 3 (dos rutas) al establo y $2+1$ a $[3]$, $[4]$ para regalar, total 6.

• El de 5 va a 4 por 3, luego a 3 y 1, total $3+2+1=6$.

• El de 3 recorre 1 al establo 1 y 9 a 6, total 10.

Entrada

• Línea 1: enteros $N$, $M$, $B$ separados por espacios.

• Líneas $2..M+1$: línea $i+1$, camino $i$ con $R_i$, $S_i$, $L_i$ separados por espacios.

• Líneas $M+2..M+B+1$: línea $M+i+1$, $P_i$, $Q_i$ separados por un espacio.

Salida

• Líneas $1..B$: línea $i$, entero, mínimo desde $P_i$ al establo por chocolate y luego a su amada en $Q_i$.

Ejemplos

Entrada 1

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

Salida 1

6
6
10

Autor del problema: Brian Hamrick, 2010