A San Valentino Farmer John distribuisce cioccolato nella stalla. $B$ tori ($1 \le B \le 25,000$) vogliono regalarlo a una mucca speciale.

Ogni animale pascola solo in uno dei $N$ pascoli ($2B \le N \le 50,000$), numerati $1..N$, uniti da $M$ sentieri bidirezionali ($N-1 \le M \le 100,000$) di varie lunghezze. Una coppia può averne diversi. Sentiero $i$ unisce $R_i$, $S_i$ ($1 \le R_i \le N; 1 \le S_i \le N$), lunghezza $L_i$ ($1 \le L_i \le 2,000$).

Toro $i$ è in $P_i$ ($1 \le P_i \le N$), dona alla mucca in $Q_i$ ($1 \le Q_i \le N$).

Trova il percorso minimo alla stalla (1), poi alla mucca. La stalla raggiunge tutti tramite sentieri e pascoli.

Esempio con 6 pascoli, 6 sentieri, 3 tori in 2, 3, 5 per le amate:

                      *1  <-- Toro vuole cioccolato per mucca nel pascolo 1
             [4]--3--[5]  <-- [5] è il numero del pascolo
            /  |
           /   |
          4    2          <-- 2 è la lunghezza del sentiero
         /     |               tra [3] e [4]
      [1]--1--[3]*6
     /   \    /
    9     3  2
   /       \/
 [6]      [2]*4

• Quello in 2 percorre 3 (due percorsi) alla stalla, poi $2+1$ a $[3]$, $[4]$ per donare, totale 6.

• Quello in 5 va a 4 per 3, poi a 3 e 1, totale $3+2+1=6$.

• Quello in 3 va per 1 alla stalla 1 e per 9 a 6, totale 10.

Input

• Riga 1: interi $N$, $M$, $B$ separati da spazi.

• Righe $2..M+1$: riga $i+1$, sentiero $i$ con $R_i$, $S_i$, $L_i$ separati da spazi.

• Righe $M+2..M+B+1$: riga $M+i+1$, $P_i$, $Q_i$ separati da uno spazio.

Output

• Righe $1..B$: riga $i$, intero, minimo da $P_i$ alla stalla per cioccolato e poi all’amata in $Q_i$.

Esempi

Input 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

Output 1

6
6
10

Autore del problema: Brian Hamrick, 2010