На День святого Валентина Farmer John раздаёт шоколад в коровнике. $B$ быков ($1 \le B \le 25,000$) хотят подарить его особым коровам.

Каждый бык и корова пасётся один на $N$ пастбищах ($2B \le N \le 50,000$), номера $1..N$. Их связывают $M$ двусторонних дорог ($N-1 \le M \le 100,000$) разных длин; между парой возможны несколько. Дорога $i$ связывает $R_i$, $S_i$ ($1 \le R_i \le N; 1 \le S_i \le N$), длина $L_i$ ($1 \le L_i \le 2,000$).

Бык $i$ живёт на $P_i$ ($1 \le P_i \le N$) и дарит корове на $Q_i$ ($1 \le Q_i \le N$).

Найдите кратчайший путь от него к коровнику (1), затем к корове. Коровник связан со всеми пастбищами через дороги и другие пастбища.

Пример: 6 пастбищ, 6 дорог, 3 быка на 2, 3, 5 дарят любимым:

                      *1  <-- Бык хочет шоколад для коровы на пастбище 1
             [4]--3--[5]  <-- [5] — номер пастбища
            /  |
           /   |
          4    2          <-- 2 — длина дороги
         /     |               между [3] и [4]
      [1]--1--[3]*6
     /   \    /
    9     3  2
   /       \/
 [6]      [2]*4

• Бык на 2 идёт 3 (два пути) к коровнику, затем $2+1$ к $[3]$, $[4]$ с подарком, всего 6.

• Бык на 5 идёт 3 к 4, затем 3 и 1, сумма $3+2+1=6$, и дарит.

• Бык на 3 идёт 1 к коровнику 1, затем 9 к 6, всего 10.

Входные данные

• Строка 1: целые $N$, $M$, $B$ через пробел.

• Строки $2..M+1$: строка $i+1$ описывает дорогу $i$ числами $R_i$, $S_i$, $L_i$ через пробел.

• Строки $M+2..M+B+1$: строка $M+i+1$ содержит $P_i$, $Q_i$ через пробел.

Выходные данные

• Строки $1..B$: строка $i$ — целое, минимум пути от $P_i$ к шоколаду в коровнике, затем к любимой на $Q_i$.

Примеры

Входные данные 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

Выходные данные 1

6
6
10

Автор задачи: Brian Hamrick, 2010