当前没有测试数据。

F - 交通

得分：$500$ 分

题目描述

AtCoder共和国有$N$个岛屿。 最初，这些岛屿之间没有机场、港口，也没有任何道路相连。 国王高桥可以在这些岛屿之间提供一些交通方式。 具体来说，他可以以任意顺序多次执行以下操作。

• 选择一个整数$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$之间建造一个双向道路。

高桥的目标是使得对于每一对不同的岛屿$U$和$V$，都可以在执行以下操作的任意次数和任意顺序下，从岛屿$U$到达岛屿$V$。

• 如果岛屿$S$和$T$都有机场，可以从岛屿$S$到达岛屿$T$。
• 如果岛屿$S$和$T$都有港口，可以从岛屿$S$到达岛屿$T$。
• 如果岛屿$S$和$T$之间有道路，可以从岛屿$S$到达岛屿$T$。

找出高桥需要支付的最小总费用，以实现他的目标。

约束

• $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$和$j$，$(A_i,B_i)\neq (A_j,B_j)$
• 输入中的所有值均为整数

---

输入

从标准输入中以以下格式给出：

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

输出

输出高桥需要支付的最小总费用。

---

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

16

高桥可以建造以下设施。

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

此时，目标可以以总费用$16$的形式实现。 无法以费用$15$或更低的形式实现此目标，因此应输出$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