거대한 소 모임

Bessie는 매년 열리는 거대한 소 모임을 준비하고 있으며, 모임을 열기에 가장 편리한 헛간을 고르려고 합니다.

모든 소는 $1$번부터 $N$번까지 번호가 매겨진 $N$개의 헛간 중 하나에 살고 있습니다. 헛간들은 $N-1$개의 길로 연결되어 있어 어떤 헛간에서든 다른 모든 헛간으로 이동할 수 있습니다. $i$번째 길은 헛간 $A_i$와 $B_i$를 잇고 길이는 $L_i$이므로, 헛간들은 하나의 트리를 이룹니다. $i$번 헛간에는 $C_i$마리의 소가 삽니다.

모임은 임의의 한 헛간에서 열 수 있습니다. 모임을 $X$번 헛간에서 열 때의 불편함은 모든 소가 $X$까지 이동해야 하는 거리의 합으로 정의됩니다. 즉, $X$로부터 거리가 $d$인 헛간에 $C_i$마리의 소가 있으면 그 헛간은 불편함에 $C_i \cdot d$만큼 기여합니다. 예를 들어 $X$에서 $20$만큼 떨어진 헛간에 소가 $3$마리 살고 있다면, 이 헛간은 불편함에 $3 \times 20 = 60$을 더합니다.

불편함의 총합이 최소가 되는 헛간을 골라, 그때의 최소 불편함을 출력하세요.

제약 조건

• $1 \le N \le 100{,}000$
• $1 \le A_i, B_i \le N$
• $1 \le L_i \le 1{,}000$
• $0 \le C_i \le 1{,}000$

• $1$번째 줄: 정수 $N$ 하나.
• $2$번째 줄부터 $N+1$번째 줄까지: $i+1$번째 줄에는 $i$번 헛간에 사는 소의 수 $C_i$가 하나씩 주어집니다.
• $N+2$번째 줄부터 $2N$번째 줄까지: 이 $N-1$개의 줄에는 각각 세 정수 $A_i$, $B_i$, $L_i$가 주어지며, 헛간 $A_i$와 $B_i$를 잇는 길이 $L_i$의 길을 나타냅니다.

• 가능한 최소 불편함을 한 줄에 출력합니다.