AT_abc270_f [ABC270F] Transportation

在 AtCoder 国有 $N$ 个岛屿，最初每个岛屿上都没有机场和港口，岛屿之间也没有道路。作为国王的高桥君决定为这些岛屿之间提供交通方式。具体来说，高桥君可以无限次地选择并执行以下三种操作之一： - 选择满足 $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$ 之间建造一条双向道路。 高桥君的目标是，使得对于任意两个不同的岛屿 $U$ 和 $V$，都可以从岛屿 $U$ 出发，通过无限次地选择并执行以下三种操作之一，到达岛屿 $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$

输出高桥君达成目标所需的最小总费用。

## 限制条件 - $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)$ - 所有输入均为整数 ## 样例解释 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$。 ## 样例解释 2 可以有机场、港口、道路三者之一未被建设的情况。 由 ChatGPT 4.1 翻译