Bessie planeja encontro anual de vacas de todo o país e quer lugar mais conveniente.

Cada vaca mora num de $N$ ($1 \le N \le 100,000$) celeiros numerados $1..N$, ligados por $N-1$ estradas com acesso entre quaisquer. Estrada $i$ liga $A_{i}$ e $B_{i}$ ($1 \le A_i \le N; 1 \le B_i \le N$), comprimento $L_{i}$ ($1 \le L_{i} \le 1,000$). Encontro em qualquer dos $N$; celeiro $i$ tem $C_{i}$ ($0 \le C_{i} \le 1,000$) vacas.

Máxima conveniência é mínimo inconveniente: em $X$, soma das distâncias de todas para $X$. Se de $i$ a $X$ são 20, total $C_{i}*20$. Ajude a escolher melhor lugar.

Cinco celeiros com quantidades variadas entre colchetes e estradas de vários comprimentos. 3 e 4 não têm vacas.

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

Pode qualquer dos cinco; tabela de inconvenientes, B1–B5 celeiros, última coluna soma.

Se encontro no 1, por celeiro:

• Celeiro 1: 0, sem viagem!
• Celeiro 2: 3, distância $2+1=3$ por 1 vaca dá 3.
• Celeiro 3: 0, sem vacas!
• Celeiro 4: 0, sem vacas!
• Celeiro 5: 14, distância $3+3+1=7$ por 2 vacas dá 14.

Total inconveniente 17.

Melhor 15, em 3, 4 ou 5.

Entrada

• Linha 1: inteiro $N$.
• Linhas $2..N+1$: linha $i+1$, inteiro $C_{i}$.
• Linhas $N+2..2N$: linha $i+N+1$, três inteiros $A_{i}$, $B_{i}$, $L_{i}$.

Saída

• Linha 1: mínimo inconveniente possível.

Exemplos

Entrada 1

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

Saída 1

15

Autor: Jeffrey Wang, de um concurso, 2010