AT_abc270_f [ABC270F] Transportation

[problemUrl]: https://atcoder.jp/contests/abc270/tasks/abc270_f AtCoder 国には $ N $ 個の島があり、 最初、どの島にも空港・港はなく、どの島の間にも道路はありません。 王である高橋君はこれらの島の間に交通手段を用意することにしました。 具体的には、高橋君は次の操作のうち $ 1 $ つを選んで行うことを好きなだけ繰り返す事ができます。 - $ 1\leq\ i\leq\ N $ をみたす $ i $ を選び、コスト $ X_i $ を払って、島 $ i $ に空港を建設する。 - $ 1\leq\ i\leq\ N $ をみたす $ i $ を選び、コスト $ Y_i $ を払って、島 $ i $ に港を建設する。 - $ 1\leq\ i\leq\ M $ をみたす $ i $ を選び、コスト $ Z_i $ を払って、島 $ A_i $ と島 $ B_i $ の間を双方向に結ぶ道路を建設する。 高橋君の目標は、任意の相異なる $ 2 $ つの島 $ U $, $ V $ について、 島 $ U $ からはじめて次の行動のうち $ 1 $ つを選んで行うことを好きなだけ繰り返す事で、 島 $ V $ に到達することができるようにする事です。 - 島 $ S,T $ の両方に空港がある時、島 $ S $ から島 $ T $ まで移動する。 - 島 $ S,T $ の両方に港がある時、島 $ S $ から島 $ T $ まで移動する。 - 島 $ S,T $ を結ぶ道路が存在する時、島 $ S $ から島 $ T $ まで移動する。 高橋君が目標を達成するのに必要な最小コストを求めてください。

N/A

N/A

### 制約 - $ 2\ \leq\ N\ \leq\ 2\times\ 10^5 $ - $ 1\ \leq\ M\ \leq\ 2\times\ 10^5 $ - $ 1\leq\ X_i\leq\ 10^9 $ - $ 1\leq\ Y_i\leq\ 10^9 $ - $ 1\leq\ A_i\