分数: 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