問題文

りんごさんは $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$ の最小全域木のコストを出力せよ。

入力例 1

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

出力例 1

22

頂点 $1$ と $2$、頂点 $1$ と $4$、頂点 $3$ と $4$ を繋ぐとそれぞれのコストは $5,8,9$ となり、合計は $22$ となります。

入力例 2

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

出力例 2

359

入力例 3

2
1000000000 1000000000
2 1 1000000000

出力例 3

3000000000