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