配点 : $1900$ 点

問題文

りんごさんは $N$ 頂点の木を持っています。 この木の $N-1$ 本の辺のうち $i$ 番目の辺は頂点 $A_i$ と頂点 $B_i$ を繋いでおり、重みは $C_i$ です。 また、頂点 $i$ には $X_i$ の重みがついています。

ここで $f(u,v)$ を、「頂点 $u$ から頂点 $v$ までの距離」と「$X_u + X_v$」の和と定めます。

$N$ 頂点の完全グラフ $G$ を考えます。 頂点 $u$ と頂点 $v$ を繋ぐ辺のコストは $f(u,v)$ です。 グラフ $G$ の最小全域木を求めて下さい。

制約

• $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$
• 与えられるグラフは木である。
• 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

$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}$

出力

グラフ $G$ の最小全域木のコストを出力せよ。

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

22

頂点 $1$ と $2$、頂点 $1$ と $4$、頂点 $3$ と $4$ を繋ぐとそれぞれのコストは $5,8,9$ となり、合計は $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