Bessie prepara raduno annuale delle mucche di tutto il paese e vuole luogo più comodo.

Ogni mucca vive in uno dei $N$ ($1 \le N \le 100,000$) fienili numerati $1..N$, collegati da $N-1$ strade rendendo tutti raggiungibili. Strada $i$ collega $A_{i}$ e $B_{i}$ ($1 \le A_i \le N; 1 \le B_i \le N$), lunghezza $L_{i}$ ($1 \le L_{i} \le 1,000$). Qualsiasi dei $N$ può ospitare; fienile $i$ ha $C_{i}$ ($0 \le C_{i} \le 1,000$) mucche.

Massima comodità significa minimo disagio: per $X$, somma delle distanze di tutte fino a $X$. Se da $i$ a $X$ distanza 20, totale $C_{i}*20$. Aiuta a scegliere il migliore.

Cinque fienili con varie quantità tra parentesi quadre e strade di varia lunghezza. 3 e 4 senza mucche.

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

Tutti e cinque possibili; tabella del disagio, B1–B5 fienili, ultima colonna somma.

Se raduno in 1, per fienile:

• Fienile 1: 0, nessun viaggio!
• Fienile 2: 3, distanza $2+1=3$ per 1 mucca dà 3.
• Fienile 3: 0, niente mucche!
• Fienile 4: 0, niente mucche!
• Fienile 5: 14, distanza $3+3+1=7$ per 2 mucche dà 14.

Disagio totale 17.

Migliore 15, in 3, 4 o 5.

Input

• Riga 1: intero $N$.
• Righe $2..N+1$: riga $i+1$, intero $C_{i}$.
• Righe $N+2..2N$: riga $i+N+1$, tre interi $A_{i}$, $B_{i}$, $L_{i}$.

Output

• Riga 1: minimo disagio possibile.

Esempi

Input 1

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

Output 1

15

Autore: Jeffrey Wang, da una gara, 2010