题目描述

AtCoder 王国有 $N$ 座岛屿. 一开始没有任何一个岛屿有机场或港口，并且没有任何道路连接它们. 高桥作为 Atcoder 王国的王国，将给这些岛屿提供一些交通手段. 具体来说，他能以任意顺序做任意次以下操作：

• 选择一个整数 $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$ 。

求高桥完成目标的最小花费.

输入格式

输入的标准格式如下：

$\begin{matrix}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 & ~ \\\end{matrix}$

输出格式

输出高桥完成目标的最小花费。

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$
• $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$ を出力します。

机翻：

高桥君建造交通工具如下。

• 支付费用 $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

空港・港・道路のうち、一度も建設されないものがあっても構いません。

机翻：

即使一些机场、港口和道路从未建成也没关系。