Bessie는 전국 소들의 연례 대모임을 준비하며 가장 편리한 장소를 원합니다.

각 소는 번호 $1..N$인 헛간 $N$개($1 \le N \le 100,000$) 중 하나에 살고 $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