اكتشف Farmer John سر أحلى زبدة في Wisconsin: السكر. بوضع مكعب في المراعي يعلم أن أبقاره الـ $N$ ($1\le N\le500$) ستلعقه وتنتج زبدة شديدة الحلاوة تباع بسعر أفضل. بالطبع ينفق المال الزائد على كماليات للأبقار.

FJ ماكر. مثل Pavlov قديمًا يعرف كيف يدربها على الذهاب لمرعى معين عند سماع الجرس. سيضع السكر هناك ويدق الجرس في منتصف فترة بعد الظهر ليعطي حلب المساء حليبًا مثاليًا.

كل بقرة تقضي وقتها في مرعى محدد، وليس بالضرورة وحدها. من المواقع والطرق اختر مرعى السكر بحيث يقل مجموع مسافات الأبقار عند دق الجرس. يعلم FJ أن اتصال الحقول يكفي لضمان حل دائمًا.

الإدخال

• السطر $1$: أعداد صحيحة بفراغات، عدد الأبقار $N$ والمراعي $P$ ($2\le P\le800$) والطرق $C$ ($1\le C\le1{,}450$). الأبقار مرقمة بشكل فريد $1\ldots N$ والمراعي $1\ldots P$.

• الأسطر $2\ldots N+1$: عدد صحيح هو مرعى بقرة؛ مرعى البقرة $i$ في السطر $i+1$.

• الأسطر $N+2\ldots N+C+1$: ثلاثة أعداد صحيحة بفراغات تحدد مرعيين وطول طريق. الطرق ثنائية الاتجاه ولا يوجد أكثر من طريق مباشر لكل زوج. أول عددين في $1\ldots P$ والثالث في $1\ldots225$.

الإخراج

• السطر $1$: عدد صحيح هو أصغر مجموع مسافات الأبقار إلى مرعى السكر.

أمثلة

الإدخال 1

3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5

الإخراج 1

8

ملاحظة

يوضح الرسم الاتصالات هندسيًا:

          P2  
 P1 @--1--@ C1
     \    |\
      \   | \
       5  7  3
        \ |   \
         \|    \ C3
       C2 @--5--@
          P3    P4

بوضع السكر في $4$ تمشي البقرة $1$ مسافة $3$ وحدات و$2$ مسافة $5$ و$3$ مسافة $0$، والمجموع $8$.

مؤلف المسألة: Greg Galperin، 2001