Bessie planuje coroczne wielkie spotkanie krów z całego kraju i chce najwygodniejsze miejsce.

Każda mieszka w jednej z $N$ ($1 \le N \le 100,000$) stodół z numerami $1..N$, połączonych $N-1$ drogami tak, że wszystkie osiągalne. Droga $i$ łączy $A_{i}$ i $B_{i}$ ($1 \le A_i \le N; 1 \le B_i \le N$), długość $L_{i}$ ($1 \le L_{i} \le 1,000$). Dowolna z $N$ może gościć; stodoła $i$ ma $C_{i}$ ($0 \le C_{i} \le 1,000$) krów.

Maksimum wygody to minimum niewygody: dla $X$ suma dróg wszystkich krów do $X$. Gdy od $i$ do $X$ dystans 20, całkowita droga $C_{i}*20$. Wybierz najlepsze.

Pięć stodół z różnymi liczbami w nawiasach kwadratowych i drogami różnych długości. 3 i 4 bez krów.

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

Każda możliwa; tabela niewygód, B1–B5 stodoły, ostatnia kolumna suma.

Przy spotkaniu w 1 dla stodół:

• Stodoła 1: 0, bez podróży!
• Stodoła 2: 3, dystans $2+1=3$ razy 1 krowa daje 3.
• Stodoła 3: 0, bez krów!
• Stodoła 4: 0, bez krów!
• Stodoła 5: 14, dystans $3+3+1=7$ razy 2 krowy daje 14.

Suma niewygody 17.

Najlepsze 15 w 3, 4 lub 5.

Wejście

• Wiersz 1: całkowita $N$.
• Wiersze $2..N+1$: wiersz $i+1$, całkowita $C_{i}$.
• Wiersze $N+2..2N$: wiersz $i+N+1$, trzy całkowite $A_{i}$, $B_{i}$, $L_{i}$.

Wyjście

• Wiersz 1: najmniejsza możliwa niewygoda.

Przykład

Wejście 1

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

Wyjście 1

15

Autor: Jeffrey Wang, z konkursu, 2010