问题描述

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$
• $(A_i,B_i)\\neq (A_j,B_j)$，若 $i\\neq 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$

输出

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

样例输入 1

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

样例输出 1

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

3 1
1 1 1
10 10 10
1 2 100

样例输出 2

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