Transportation

题目描述

共和国 AtCoder 有 $N$ 个岛屿。 最初，所有岛屿都没有机场也没有港口，并且任意两座岛屿之间都没有道路。 国王 Takahashi 将提供一些岛屿间的交通方式。 具体来说，他可以任意次且按任意顺序执行下述操作。

选择一个整数 $i$ 满足 $1\leq i\leq N$ 并支付费用 $X_i$ 在岛屿 $i$ 建造机场。 选择一个整数 $i$ 满足 $1\leq i\leq N$ 并支付费用 $Y_i$ 在岛屿 $i$ 建造港口。 选择一个整数 $i$ 满足 $1\leq i\leq M$ 并支付费用 $Z_i$ 建造一条双向道路，连接岛屿 $A_i$ 和岛屿 $B_i$。

Takahashi 的目标是使得对任意不同的两座岛屿 $U$ 和 $V$，在可以任意次且按任意顺序执行下列操作的情况下，都能从岛屿 $U$ 到达岛屿 $V$。

当岛屿 $S$ 和 $T$ 都有机场时，可以从岛屿 $S$ 前往岛屿 $T$。 当岛屿 $S$ 和 $T$ 都有港口时，可以从岛屿 $S$ 前往岛屿 $T$。 当岛屿 $S$ 和 $T$ 由一条道路相连时，可以从岛屿 $S$ 前往岛屿 $T$。

求 Takahashi 为实现目标所需支付的最小总费用。

输入格式

输入按下述格式由标准输入给出： $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$

输出格式

输出 Takahashi 为实现目标所需支付的最小总费用。

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$ $(A_i,B_i)\neq (A_j,B_j)$，如果 $i\neq j$。 输入中的所有数值均为整数。Takahashi 将建造以下基础设施。

支付费用 $X_1=1$ 在岛屿 $1$ 建造机场。 支付费用 $X_3=4$ 在岛屿 $3$ 建造机场。 支付费用 $Y_2=2$ 在岛屿 $2$ 建造港口。 支付费用 $Y_4=3$ 在岛屿 $4$ 建造港口。 支付费用 $Z_2=6$ 建造一条连接岛屿 $1$ 和岛屿 $4$ 的道路。

然后，目标可在总费用 $16$ 下实现。 不存在以不超过 $15$ 的费用实现目标的方法，所以应当输出 $16$。
并不要求三种设施都至少建造一次。

标签: AtCoder|abc270F

来源

AtCoder|abc270F