AT_cf17_final_j Tree MST

[problemUrl]: https://atcoder.jp/contests/cf17-final/tasks/cf17_final_j りんごさんは $ 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/A

N/A

### 制約 - $ 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 $ となります。