← 返回题目列表

Codeforces · 1095/F

F. 使其连接

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

给你一个由 $$$n$$$ 个顶点组成的无向图。每个顶点上都写有一个数字;顶点 $$$i$$$ 上的数字是 $$$a_i$$$。最初图中没有边。

您可以向该图添加一些边,但您必须为此付费。在顶点 $$$x$$$ 和 $$$y$$$ 之间添加边的成本是 $$$a_x + a_y$$$ 硬币。还有$$$m$$$特别优惠,每个优惠由三个数字$$$x$$$、$$$y$$$和$$$w$$$表示,表示您可以添加一条连接顶点$$$x$$$和$$$y$$$的边,并为此支付$$$w$$$硬币。您不必使用特别优惠:如果有一对顶点 $$$x$$$ 和 $$$y$$$ 具有与之关联的特别优惠,您仍然可以为其支付 $$$a_x + a_y$$$ 硬币来连接这两个顶点。

使图形连接起来至少需要花费多少硬币?回想一下,如果可以仅使用属于该图的边从任何顶点到任何其他顶点,则该图是连通的。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le 2 \cdot 10^5$$$) — 分别是图中的顶点数和特价商品的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$) — 写在顶点上的数字。

接下来是 $$$m$$$ 行,每行包含三个整数 $$$x$$$、$$$y$$$ 和 $$$w$$$ ($$$1 \le x, y \le n$$$, $$$1 \le w \le 10^{12}$$$, $$$x \ne y$$$) 表示特价:您可以添加连接顶点的边$$$x$$$ 和顶点 $$$y$$$,这条边将花费 $$$w$$$ 硬币。

输出

打印一个整数——连接图表所需支付的最少硬币数量。

示例

输入 #1

3 2
1 3 3
2 3 5
2 1 1

输出 #1

5

输入 #2

4 0
1 3 3 7

输出 #2

16

输入 #3

5 4
1 2 3 4 5
1 2 8
1 3 10
1 4 7
1 5 15

输出 #3

18

注意

在第一个示例中,可以使用特别优惠 $$$2$$$ 将 $$$1$$$ 连接到 $$$2$$$,然后在不使用任何优惠的情况下将 $$$1$$$ 连接到 $$$3$$$。

在接下来的两个示例中,无需使用特殊优惠即可获得最佳答案。