تكاسل Farmer John عن صيانة الطرق التي تصل إلى كل مراعيه الـ $N$ ($5\le N\le10{,}000$)، المرقمة $1\ldots N$. كل مرعى موطن بقرة واحدة. سيحذف أكبر عدد من طرقه الـ $P$ ($N-1\le P\le100{,}000$) مع إبقاء الاتصال. حدد طرق $N-1$ المتبقية.

الطريق ثنائي الاتجاه $j$ يصل $S_j,E_j$ ($1\le S_j\le N;1\le E_j\le N;S_j\ne E_j$)، ويستغرق $L_j$ ($0\le L_j\le1{,}000$). لكل زوج طريق مباشر واحد على الأكثر.

الأبقار حزينة لتقليص النقل. زر كلًا منها مرة على الأقل يوميًا لإسعادها. كل زيارة إلى $i$، حتى المرور، تتطلب محادثة البقرة لمدة $C_i$ ($1\le C_i\le1{,}000$).

تنام كل ليلة في نفس المرعى الذي تختاره حتى تتعافى الأبقار من حزنها. تحادث بقرته على الأقل صباحًا عند الاستيقاظ ومساء عند العودة للنوم.

إذا أبقى FJ الطرق المقترحة واخترت أفضل مرعى للنوم، حدد أقل وقت يومي لزيارة كل بقرة مرة على الأقل.

في أول $10$ إرسالات ستتلقى نتائج التشغيل على جزء من البيانات الحقيقية.

الإدخال

• السطر $1$: العددان الصحيحان $N,P$ بفراغ.

• الأسطر $2\ldots N+1$: السطر $i+1$، عدد صحيح $C_i$.

• الأسطر $N+2\ldots N+P+1$: السطر $N+j+1$، الأعداد الصحيحة $S_j,E_j,L_j$ بفراغات.

الإخراج

• السطر $1$: عدد صحيح، الوقت الكلي شاملاً زيارتين لبقرة مرعى النوم.

أمثلة

الإدخال 1

5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6
4 5 12

الإخراج 1

176

ملاحظة

              +-(15)-+
             /        \
            /          \
     1-(5)-2-(5)-3-(6)--5
            \   /(17)  /
         (12)\ /      /(12)
              4------+

أبق هذه الطرق:

     1-(5)-2-(5)-3      5
            \          /
         (12)\        /(12)
             *4------+

استيقظ في $4$ وزر $4,5,4,2,3,2,1,2,4$ مستغرقًا $176$ قبل النوم.

المهام الفرعية

النقاط: $300$

مؤلفا المسألة: David Benjamin وJacob Steinhardt، 2008