题目描述

有 $n$ 个点，如下操作：

• 对于 $1\le i\le n$，可以花 $x_i$ 的贡献 $i$ 号点建一个机场。
• 对于 $1\le i\le n$，可以花 $y_i$ 的贡献在 $i$ 号点建一个港口。
• 对于 $1\le i\le m$，可以花 $z_i$ 的贡献在 $a_i$ 号点到 $b_i$ 号点连一条无向边。

如果两个点 $u,v$ 满足下列条件之一，则 $u,v$ 可以互相到达：

• $u,v$ 都有机场
• $u,v$ 都有港口
• $u$ 到 $v$ 有边

问至少花多少代价才能让所有点连通。

输入格式

第一行输入两个正整数 $n,m$

接下来一行输入 $x_1,x_2,\cdots,x_n$ 代表在每个点建立机场的花费

接下来一行输入 $y_1,y_2,\cdots,y_n$ 代表在每个点建立港口的花费

接下来 $m$ 行，每行三个整数 $u,v,w$ 代表$u,v$ 之间有一条长度为 $w$ 的边。

输出格式

输出最小的花费

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\ u_i\ <\ v_i\leq\ N$
• $1\leq\ w_i\leq\ 10^9$

Sample Explanation 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$ 。