Score : $500$ points

问题描述

在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需要支付的最小总成本以实现他的目标。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

The Republic of AtCoder has $N$ islands. Initially, none of the islands has an airport or harbor, and there is no road between any two of them. Takahashi, the king, will provide some means of transportation between these islands. Specifically, he can do the following operations any number of times in any order.

• Choose an integer $i$ such that $1\leq i\leq N$ and pay a cost of $X_i$ to build an airport on island $i$.
• Choose an integer $i$ such that $1\leq i\leq N$ and pay a cost of $Y_i$ to build a harbor on island $i$.
• Choose an integer $i$ such that $1\leq i\leq M$ and pay a cost of $Z_i$ to build a road that bidirectionally connects island $A_i$ and island $B_i$.

Takahashi's objective is to make it possible, for every pair of different islands $U$ and $V$, to reach island $V$ from island $U$ when one can perform the following actions any number of times in any order.

• When islands $S$ and $T$ both have airports, go from island $S$ to island $T$.
• When islands $S$ and $T$ both have harbors, go from island $S$ to island $T$.
• When islands $S$ and $T$ are connected by a road, go from island $S$ to island $T$.

Find the minimum total cost Takahashi needs to pay to achieve his objective.

Constraints

• $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)$, if $i\neq j$.
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$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$

Output

Print the minimum total cost Takahashi needs to pay to achieve his objective.

Sample Input 1

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

Sample Output 1

16

Takahashi will build the following infrastructure.

• Pay a cost of $X_1=1$ to build an airport on island $1$.
• Pay a cost of $X_3=4$ to build an airport on island $3$.
• Pay a cost of $Y_2=2$ to build a harbor on island $2$.
• Pay a cost of $Y_4=3$ to build a harbor on island $4$.
• Pay a cost of $Z_2=6$ to build a road connecting island $1$ and island $4$.

Then, the objective will be achieved at a cost of $16$. There is no way to achieve the objective for a cost of $15$ or less, so $16$ should be printed.

Sample Input 2

3 1
1 1 1
10 10 10
1 2 100

Sample Output 2

3

It is not mandatory to build all three types of facilities at least once.

Sample Input 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

Sample Output 3

160

update @ 2024/3/10 11:24:10