题目描述

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$ $M$ $X_1$ $X_2$ $\ldots$ $X_N$ $Y_1$ $Y_2$ $\ldots$ $Y_N$ $A_1$ $B_1$ $Z_1$ $A_2$ $B_2$ $Z_2$ $\vdots$ $A_M$ $B_M$ $Z_M$

输出格式

高橋君が目標を達成するのに必要な最小コストを出力せよ。

题目大意

有 $n$ 个点，如下操作：

• 对于 $1\le i\le n$，可以花 $x_i$ 的贡 $i$ 号点建一个机场 .
• 对于 $1\le i\le n$，可以花 $y_i$ 的贡献在 $i$ 号点建一个港口 .
• 对于 $1\le i\le n$，可以花 $z_i$ 的贡献在 $a_i$ 号点到 $b_i$ 号点连一条无向边 .

如果两个点 $u,v$ 满足下列条件之一，则 $u,v$ 可以互相到达：

• $u,v$ 都有机场 .
• $u,v$ 都有港口 .
• $u$ 到 $v$ 有边 .

问至少花多少代价才能让所有点连通 .

$1\le n,m\le 2\times 10^5$，$1\le x_i,y_i,z_i\le 10^9$ .

4 2
1 20 4 7
20 2 20 3
1 3 5
1 4 6

16

3 1
1 1 1
10 10 10
1 2 100

3

7 8
35 29 36 88 58 15 25
99 7 49 61 67 4 57
2 3 3
2 5 36
2 6 89
1 6 24
5 7 55
1 3 71
3 4 94
5 6 21

160

提示

制約

• $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\ <\ B_i\leq\ N$
• $1\leq\ Z_i\leq\ 10^9$
• $i\neq\ j$ ならば $(A_i,B_i)\neq\ (A_j,B_j)$
• 入力は全て整数

Sample Explanation 1

高橋君は次のように交通手段を建設します。 - コスト $X_1=1$ を払って、島 $1$ に空港を建設する。 - コスト $X_3=4$ を払って、島 $3$ に空港を建設する。 - コスト $Y_2=2$ を払って、島 $2$ に港を建設する。 - コスト $Y_4=3$ を払って、島 $4$ に港を建設する。 - コスト $Z_2=6$ を払って、島 $1$ と島 $4$ の間を結ぶ道路を建設する。 このとき、目標は達成されており、かかったコストは $16$ となります。 コスト $15$ 以下で目標を達成する方法はないため、$16$ を出力します。

Sample Explanation 2

空港・港・道路のうち、一度も建設されないものがあっても構いません。