Bessie מתכננת מפגש שנתי גדול לפרות מכל הארץ ורוצה המקום הנוח ביותר.

כל פרה גרה באחד מ-$N$ ($1 \le N \le 100,000$) אסמים ממוספרים $1..N$, מחוברים ב-$N-1$ דרכים וכולם נגישים מכולם. דרך $i$ מחברת $A_{i}$ ו-$B_{i}$ ($1 \le A_i \le N; 1 \le B_i \le N$), אורך $L_{i}$ ($1 \le L_{i} \le 1,000$). כל אחד מ-$N$ יכול לארח; באסם $i$ יש $C_{i}$ ($0 \le C_{i} \le 1,000$) פרות.

מרב נוחות הוא מזער אי-נוחות: ל-$X$, סכום מרחקי כל הפרות ל-$X$. אם מ-$i$ ל-$X$ מרחק 20, המרחק הכולל $C_{i}*20$. בחרו הטוב ביותר.

חמישה אסמים עם כמויות שונות בסוגריים מרובעים ודרכים באורכים שונים. ב-3 ו-4 אין פרות.

      1     3     4     5
      @--1--@--3--@--3--@[2]
     [1]    |
            2
            |
            @[1]
            2

אפשר בכל החמישה; טבלת אי-נוחות, B1–B5 אסמים והאחרון סכום.

אם המפגש ב-1, לכל אסם:

• אסם 1: 0, אין נסיעה!
• אסם 2: 3, מרחק $2+1=3$ כפול פרה אחת נותן 3.
• אסם 3: 0, אין פרות!
• אסם 4: 0, אין פרות!
• אסם 5: 14, מרחק $3+3+1=7$ כפול שתי פרות נותן 14.

סך אי-נוחות 17.

הטוב ביותר 15, אפשר ב-3, 4, 5.

קלט

• שורה 1: שלם $N$.
• שורות $2..N+1$: שורה $i+1$ שלם $C_{i}$.
• שורות $N+2..2N$: שורה $i+N+1$ שלושה שלמים $A_{i}$, $B_{i}$, $L_{i}$.

פלט

• שורה 1: אי-נוחות מזערית אפשרית.

דוגמאות

קלט 1

5
1
1
0
0
2
1 3 1
2 3 2
3 4 3
4 5 3

פלט 1

15

מחבר: Jeffrey Wang, מתחרות, 2010