No Dia dos Namorados Farmer John distribui chocolate no celeiro. $B$ touros ($1 \le B \le 25,000$) querem dar a uma vaca especial.

Cada touro e vaca pasta sozinho num dos $N$ pastos ($2B \le N \le 50,000$), numerados $1..N$, ligados por $M$ caminhos bidirecionais ($N-1 \le M \le 100,000$) de comprimentos variados. Pode haver vários por par. Caminho $i$ liga $R_i$, $S_i$ ($1 \le R_i \le N; 1 \le S_i \le N$), comprimento $L_i$ ($1 \le L_i \le 2,000$).

Touro $i$ está em $P_i$ ($1 \le P_i \le N$), presenteia a vaca em $Q_i$ ($1 \le Q_i \le N$).

Ache a menor rota ao celeiro (1), depois à vaca. O celeiro alcança todos via caminhos e pastos.

Exemplo com 6 pastos, 6 caminhos, 3 touros em 2, 3, 5 para suas amadas:

                      *1  <-- Touro quer chocolate para vaca do pasto 1
             [4]--3--[5]  <-- [5] é o número do pasto
            /  |
           /   |
          4    2          <-- 2 é o comprimento do caminho
         /     |               entre [3] e [4]
      [1]--1--[3]*6
     /   \    /
    9     3  2
   /       \/
 [6]      [2]*4

• O de 2 anda 3 (duas rotas) ao celeiro e $2+1$ a $[3]$, $[4]$ para dar, total 6.

• O de 5 vai a 4 por 3, depois a 3 e 1, total $3+2+1=6$.

• O de 3 anda 1 ao celeiro 1 e 9 a 6, total 10.

Entrada

• Linha 1: inteiros $N$, $M$, $B$ separados por espaços.

• Linhas $2..M+1$: linha $i+1$, caminho $i$ com $R_i$, $S_i$, $L_i$ separados por espaços.

• Linhas $M+2..M+B+1$: linha $M+i+1$, $P_i$, $Q_i$ separados por um espaço.

Saída

• Linhas $1..B$: linha $i$, inteiro, mínimo de $P_i$ ao celeiro pelo chocolate e à amada em $Q_i$.

Exemplos

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

Saída 1

6
6
10

Créditos do problema: Brian Hamrick, 2010