W walentynki Farmer John rozdaje czekoladę w oborze, a $B$ byków ($1 \le B \le 25,000$) ma szczególną krowę, której chce ją podarować.

Każdy byk i krowa pasie się samotnie na jednym z $N$ pastwisk ($2B \le N \le 50,000$), numerowanych $1..N$, połączonych $M$ dwukierunkowymi ścieżkami ($N-1 \le M \le 100,000$) o różnych długościach. Parę może łączyć bezpośrednio kilka ścieżek. Ścieżka $i$ łączy $R_i$, $S_i$ ($1 \le R_i \le N; 1 \le S_i \le N$), długość $L_i$ ($1 \le L_i \le 2,000$).

Byk $i$ jest na $P_i$ ($1 \le P_i \le N$) i obdarowuje krowę na $Q_i$ ($1 \le Q_i \le N$).

Znajdź najkrótszą drogę z obecnego pastwiska do obory (1), a potem do ukochanej. Z obory można dotrzeć do wszystkich pastwisk, ewentualnie przez inne ścieżki i pastwiska.

Przykład: 6 pastwisk, 6 ścieżek, 3 byki na 2, 3, 5 obdarowują ukochane:

                      *1  <-- Byk chce czekolady dla krowy na pastwisku 1
             [4]--3--[5]  <-- [5] jest numerem pastwiska
            /  |
           /   |
          4    2          <-- 2 jest długością ścieżki
         /     |               między [3] a [4]
      [1]--1--[3]*6
     /   \    /
    9     3  2
   /       \/
 [6]      [2]*4

• Byk z 2 idzie 3 (dwie trasy) do obory, potem $2+1$ do $[3]$, $[4]$, by dać czekoladę, łącznie 6.

• Byk z 5 idzie do 4 za 3, potem do 3 i 1, łącznie $3+2+1=6$, by dać czekoladę.

• Byk z 3 idzie 1 do obory 1, a potem z czekoladą 9 do 6, łącznie 10.

Wejście

• Wiersz 1: liczby całkowite $N$, $M$, $B$ oddzielone spacjami.

• Wiersze $2..M+1$: wiersz $i+1$ opisuje ścieżkę $i$ liczbami $R_i$, $S_i$, $L_i$ oddzielonymi spacjami.

• Wiersze $M+2..M+B+1$: wiersz $M+i+1$ zawiera $P_i$, $Q_i$ oddzielone spacją.

Wyjście

• Wiersze $1..B$: wiersz $i$, jedna liczba całkowita, minimalna droga byka z $P_i$ po czekoladę do obory i potem do wymarzonej krowy na $Q_i$.

Przykład

Wejście 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

Wyjście 1

6
6
10

Autor zadania: Brian Hamrick, 2010