YATP

트리 문제를 하나 더 풀어 보자. 노드마다 벌점이 있고 간선마다 가중치가 있는 트리가 주어진다. 두 노드를 잇는 단순 경로의 비용은 그 경로에 속한 간선 가중치의 합에 양 끝 노드의 벌점을 곱한 값을 더한 것이다. 노드 $u$와 노드 $v$를 잇는 경로의 비용은 $\mathrm{dist}(u, v) + p_u \times p_v$이며, $\mathrm{dist}(u, v)$는 경로에 속한 간선 가중치의 합, $p_u$는 노드 $u$의 벌점이다.

간선을 하나도 지나지 않는 경로도 경로로 친다. 이런 경로의 비용은 그 노드 벌점의 제곱, 즉 $p_u^2$이다.

각 노드마다 그 노드에서 시작하는 경로의 비용 중 최솟값을 구한다. 최종 답은 모든 노드의 최솟값을 더한 값이다.

입력은 테스트 케이스 하나로 이루어진다.

첫째 줄에 노드의 개수 $n$이 주어진다. ($1 \le n \le 200{,}000$)

둘째 줄에 각 노드의 벌점 $p$가 노드 번호 순서대로 공백으로 구분되어 $n$개 주어진다. ($1 \le p \le 1{,}000{,}000$)

이어지는 $n - 1$개의 줄에는 정수 $i$, $j$, $w$가 공백으로 구분되어 주어진다. 이는 노드 $i$와 노드 $j$를 잇는 가중치 $w$의 간선을 뜻한다. ($1 \le i \le n$, $1 \le j \le n$, $i \ne j$, $1 \le w \le 1{,}000{,}000$)

모든 노드의 최소 비용을 더한 값을 정수 하나로 출력한다.