题目描述

りんごさんは $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$ の最小全域木を求めて下さい。

输入格式

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

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

题目大意

给定一棵 $n$ 个节点的树，现有有一张完全图，两点 $x,y$ 之间的边长为 $w_x+w_y+dis_{x,y}$，其中 $dis$ 表示树上两点的距离。

求完全图的最小生成树。

$n \leq 2 \times 10^5$。

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

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

提示

制約

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

Sample Explanation 1

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