题目描述

​ 有 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 。 ​ 第二行 n 个整数 $x_{1\sim n}$ 。 ​ 第三行 n 个整数$y_{1\sim n}$。 ​ 之后 m 行，每行给出$a_i,b_i,z_i$。 ​

输出格式

​ 一行，一个整数，表示答案。 ​

样例

​

样例输入

​

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

​

样例输出

​

16

​

样例解释

​ 在$2,4$建立港口，连接$(1,3),(1,4)$ 。 ​

数据范围与提示

​ 对于 30% 的数据， $1 \leq n,m\leq 10^3$。 ​ 对于 100% 的数据，$ 1 \leq n,m \leq 2 \times 10^5,1 \leq x_i,y_i,z_i \leq 10^9 $。 ​