交通建设

题目描述

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

求高桥为实现目标需要支付的最小总费用。

输入格式

输入按以下格式从标准输入给出:

$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

数据范围

• $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\lt B_i\leq N$
• $1\leq Z_i\leq 10^9$
• 若 $i\neq j$,则 $(A_i,B_i)\neq (A_j,B_j)$。
• 输入中的所有值均为整数。