Score : $1900$ points

Problem Statement

Ringo has a tree with $N$ vertices. The $i$-th of the $N-1$ edges in this tree connects Vertex $A_i$ and Vertex $B_i$ and has a weight of $C_i$. Additionally, Vertex $i$ has a weight of $X_i$.

Here, we define $f(u,v)$ as the distance between Vertex $u$ and Vertex $v$, plus $X_u + X_v$.

We will consider a complete graph $G$ with $N$ vertices. The cost of its edge that connects Vertex $u$ and Vertex $v$ is $f(u,v)$. Find the minimum spanning tree of $G$.

Constraints

• $2 \leq N \leq 200,000$
• $1 \leq X_i \leq 10^9$
• $1 \leq A_i,B_i \leq N$
• $1 \leq C_i \leq 10^9$
• The given graph is a tree.
• All input values are integers.

Input

Input is given from Standard Input in the following format:

$N$

$X_1$ $X_2$ $...$ $X_N$

$A_1$ $B_1$ $C_1$

$A_2$ $B_2$ $C_2$

$:$

$A_{N-1}$ $B_{N-1}$ $C_{N-1}$

Output

Print the cost of the minimum spanning tree of $G$.

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

22

We connect the following pairs: Vertex $1$ and $2$, Vertex $1$ and $4$, Vertex $3$ and $4$. The costs are $5$, $8$ and $9$, respectively, for a total of $22$.

6
44 23 31 29 32 15
1 2 10
1 3 12
1 4 16
4 5 8
4 6 15

359

2
1000000000 1000000000
2 1 1000000000

3000000000