Vào ngày lễ tình nhân, Farmer John phát sô cô la ở chuồng, và $B$ bò đực ($1 \le B \le 25,000$) mỗi con có một bò cái đặc biệt để tặng.

Mỗi con bò ăn cỏ một mình tại một trong $N$ đồng cỏ ($2B \le N \le 50,000$), đánh số $1..N$, nối bởi $M$ đường hai chiều ($N-1 \le M \le 100,000$) dài khác nhau. Có thể có nhiều đường nối trực tiếp một cặp. Đường $i$ nối $R_i$, $S_i$ ($1 \le R_i \le N; 1 \le S_i \le N$), dài $L_i$ ($1 \le L_i \le 2,000$).

Bò đực $i$ ở $P_i$ ($1 \le P_i \le N$), muốn tặng bò cái tại $Q_i$ ($1 \le Q_i \le N$).

Tìm đường ngắn nhất từ đồng cỏ hiện tại tới chuồng (đồng cỏ 1), rồi tới bò cái đặc biệt. Từ chuồng có thể tới mọi đồng cỏ, có thể qua các đường và đồng cỏ khác.

Ví dụ có 6 đồng cỏ, 6 đường, 3 bò đực ở 2, 3, 5 muốn tặng người yêu:

                      *1  <-- Bò đực muốn sô cô la cho bò cái ở đồng cỏ 1
             [4]--3--[5]  <-- [5] là số hiệu đồng cỏ
            /  |
           /   |
          4    2          <-- 2 là độ dài đường
         /     |               giữa [3] và [4]
      [1]--1--[3]*6
     /   \    /
    9     3  2
   /       \/
 [6]      [2]*4

• Bò ở 2 đi khoảng cách 3 (hai cách) tới chuồng, rồi $2+1$ tới $[3]$, $[4]$ để tặng, tổng 6.

• Bò ở 5 đi tới 4 khoảng cách 3, rồi tới 3 và 1, tổng $3+2+1=6$ để tặng.

• Bò ở 3 đi 1 tới chuồng 1 rồi mang sô cô la đi thêm 9 tới 6, tổng 10.

Dữ liệu vào

• Dòng 1: các số nguyên $N$, $M$, $B$ cách nhau bằng dấu cách.

• Các dòng $2..M+1$: dòng $i+1$ mô tả đường $i$ bằng $R_i$, $S_i$, $L_i$ cách nhau bằng dấu cách.

• Các dòng $M+2..M+B+1$: dòng $M+i+1$ chứa $P_i$, $Q_i$ cách nhau bằng dấu cách.

Dữ liệu ra

• Các dòng $1..B$: dòng $i$ chứa một số nguyên, khoảng cách nhỏ nhất bò tại $P_i$ đi lấy sô cô la ở chuồng rồi tặng bò cái trong mơ tại $Q_i$.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

6
6
10

Tác giả bài toán: Brian Hamrick, 2010