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$

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

16

输入输出样例 #2

输入 #2

3 1
1 1 1
10 10 10
1 2 100

输出 #2

3

输入输出样例 #3

输入 #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

输出 #3

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)$
• 所有输入均为整数

样例解释 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 翻译