← 返回题目列表

AtCoder · abc270_f

I. 运输

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

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, 到达岛屿 V 来自岛屿 U 当一个人可以以任何顺序执行以下操作任意次数时。

  • 当岛屿 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