Bessie planea reunión anual de vacas de todo el país y quiere ubicación más conveniente.

Cada vaca vive en uno de $N$ ($1 \le N \le 100,000$) graneros numerados $1..N$, conectados por $N-1$ caminos con acceso entre cualquiera. Camino $i$ conecta $A_{i}$ y $B_{i}$ ($1 \le A_i \le N; 1 \le B_i \le N$), longitud $L_{i}$ ($1 \le L_{i} \le 1,000$). Reunión en cualquiera de $N$; granero $i$ tiene $C_{i}$ ($0 \le C_{i} \le 1,000$) vacas.

Máxima conveniencia es mínima inconveniencia. Para $X$ es suma de distancias que recorren todas a $X$; distancia de $i$ a $X$ 20 da recorrido $C_{i}*20$. Ayuda a elegir el mejor.

Cinco graneros con cantidades variadas entre corchetes y caminos de longitudes distintas. 3 y 4 sin vacas.

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

Cualquiera de cinco sirve; tabla de inconveniencias, B1–B5 graneros, última columna total.

Si reunión en 1, por granero:

• Granero 1: 0, sin viaje.
• Granero 2: 3, distancia $2+1=3$ por 1 vaca da 3.
• Granero 3: 0, sin vacas.
• Granero 4: 0, sin vacas.
• Granero 5: 14, distancia $3+3+1=7$ por 2 vacas da 14.

Total inconveniencia 17.

Mejor posible 15, en 3, 4 o 5.

Entrada

• Línea 1: entero $N$.
• Líneas $2..N+1$: línea $i+1$, entero $C_{i}$.
• Líneas $N+2..2N$: línea $i+N+1$, tres enteros $A_{i}$, $B_{i}$, $L_{i}$.

Salida

• Línea 1: inconveniencia mínima posible.

Ejemplos

Entrada 1

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

Salida 1

15

Autor: Jeffrey Wang, de un concurso, 2010