تسعى Bessie دائمًا لتحسين حياتها، واكتشفت أنها تحب زيارة $F$ مراعي مفضلة $F_i$ من أصل $P$ مرعى يملكها Farmer John. أرقام المراعي $1,\ldots,P$؛ $1\le F\le P$، $1\le P\le500$، $1\le F_i\le P$.

تصل $C$ طرق ثنائية الاتجاه المراعي (أرقامها $1,\ldots,C$، $1\le C\le8,000$) وتتيح الوصول لأي مرعى. للطريق $P_i$ طرفان $a_i,b_i$ ($1\le a_i,b_i\le P$) وزمن عبور $T_i$ ($1\le T_i\le892$) في أي اتجاه.

تبحث عن رقم أفضل مرعى للنوم بحيث يقل متوسط زمن الوصول إلى مراعيها المفضلة $F$ بعد الاستيقاظ.

في خريطة المثال تحدد النجوم المراعي المفضلة، والأعداد بين الأقواس المربعة أزمنة الطرق.

            1*--[4]--2--[2]--3
                     |       |
                    [3]     [4]
                     |       |
                     4--[3]--5--[1]---6---[6]---7--[7]--8*
                     |       |        |         |
                    [3]     [2]      [1]       [3]
                     |       |        |         |
                    13*      9--[3]--10*--[1]--11*--[3]--12*

يبين الجدول المسافات للمرشحين 4,5,6,7,9,10,11,12:

                       * * * * * * Favorites * * * * * *
 Potential      Pasture Pasture Pasture Pasture Pasture Pasture     Average
Best Pasture       1       8      10      11      12      13        Distance
------------      --      --      --      --      --      --      -----------
    4              7      16       5       6       9       3      46/6 = 7.67
    5             10      13       2       3       6       6      40/6 = 6.67
    6             11      12       1       2       5       7      38/6 = 6.33
    7             16       7       4       3       6      12      48/6 = 8.00
    9             12      14       3       4       7       8      48/6 = 8.00
   10             12      11       0       1       4       8      36/6 = 6.00 ** BEST
   11             13      10       1       0       3       9      36/6 = 6.00
   12             16      13       4       3       0      12      48/6 = 8.00

بافتراض أن هذه الخيارات تشمل الأفضل (على البرنامج فحص جميع المراعي بطريقة ما)، يكون المرعى 10 أفضل موضع للنوم.

الإدخال

• السطر 1: $P,F,C$ بمسافات.
• الأسطر $2,\ldots,F+1$: السطر $i+2$ يحتوي العدد الصحيح $F_i$.
• الأسطر $F+2,\ldots,C+F+1$: السطر $i+F+1$ يصف الطريق $i$ بالأعداد $a_i,b_i,T_i$ مفصولة بمسافات.

الإخراج

• السطر 1: رقم صحيح لأفضل مرعى للنوم. عند التعادل اختر أصغر رقم.

أمثلة

الإدخال 1

13 6 15
11
13
10
12
8
1
2 4 3
7 11 3
10 11 1
4 13 3
9 10 3
2 3 2
3 5 4
5 9 2
6 7 6
5 6 1
1 2 4
4 5 3
11 12 3
6 10 1
7 8 7

الإخراج 1

10

ملاحظة

كما في نص المسألة

كما في نص المسألة.

صاحب المسألة: Rob Kolstad، 2009