يوزع 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 يسير إلى 4 مسافة 3 ثم إلى 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