AT_arc029_3.[ARC029C] 高橋君と国家

高桥君正在游戏中经营一个国家。

国家有 $N$ 个城市和 $M$ 条道路。每条道路直接连接两个不同的城市，且道路中间没有其他城市。此外，任意两个城市之间，直接连接它们的道路最多只有一条。

最初，所有道路都未铺设，所有城市也都没有设置交易所。

为了国家的发展，高桥君决定铺设道路并设置交易所。

对于每个城市，只要满足以下任一条件，国家就被认为处于“良好状态”：

• 该城市设置了交易所。
• 该城市没有设置交易所，但可以仅通过已铺设的道路到达设置了交易所的其他城市。

城市编号为 $1$ 到 $N$，道路编号为 $1$ 到 $M$。在城市 $i$ 设置交易所需要 $c_i$ 枚金币。铺设第 $i$ 条道路需要 $r_i$ 枚金币。

由于金币有限，请你求出使国家处于“良好状态”所需金币的最小总数。

输入通过标准输入给出，格式如下：

$N$ $M$
$c_1$
$c_2$
$\vdots$
$c_N$
$a_1$ $b_1$ $r_1$
$a_2$ $b_2$ $r_2$
$\vdots$
$a_M$ $b_M$ $r_M$

• 第 $1$ 行包含两个整数 $N\ (2 \leq N \leq 100\,000)$ 和 $M\ (1 \leq M \leq 200\,000)$，表示有 $N$ 个城市和 $M$ 条道路。
• 第 $2$ 行到第 $N+1$ 行，每行一个整数 $c_i\ (1 \leq c_i \leq 1\,000\,000\,000)$，表示在城市 $i$ 设置交易所需要的金币数。
• 第 $N+2$ 行到第 $N+M+1$ 行，每行三个整数 $a_i$, $b_i\ (1 \leq a_i < b_i \leq N)$, $r_i\ (1 \leq r_i \leq 1\,000\,000\,000)$，表示第 $i$ 条道路连接城市 $a_i$ 和 $b_i$，铺设该道路的花费为 $r_i$。

请输出使国家处于“良好状态”所需的最小金币总数。输出应以换行符结尾。

部分分

本题设有部分分。

• 若能通过满足 $N \leq 8$ 且 $M \leq 10$ 的数据集 1，则可获得 10 分。
• 若能通过满足 $N \leq 12$ 且 $M \leq 66$ 的数据集 2，则可获得额外 20 分。
• 若能通过满足 $N \leq 3\,000$ 且 $M \leq 6\,000$ 的数据集 3，则可获得额外 30 分。
• 若能通过无额外限制的数据集 4，则可获得额外 40 分。

样例解释 1

城市和道路的布局如下图所示。

按如下方式设置交易所和铺设道路：

• 在城市 $1$ 设置交易所，花费 $40$ 枚金币。
• 在城市 $3$ 设置交易所，花费 $30$ 枚金币。
• 在城市 $5$ 设置交易所，花费 $70$ 枚金币。
• 铺设道路 $1$（连接城市 $1$ 和 $2$），花费 $40$ 枚金币。
• 铺设道路 $3$（连接城市 $1$ 和 $4$），花费 $60$ 枚金币。
• 铺设道路 $7$（连接城市 $5$ 和 $6$），花费 $60$ 枚金币。
• 铺设道路 $8$（连接城市 $6$ 和 $7$），花费 $50$ 枚金币。

最终城市和道路的状态如下图所示。图中，设置了交易所的城市用双线框表示，铺设的道路用双线表示。

此时，国家处于“良好状态”。具体来说：

• 城市 $1$ 设置了交易所。
• 城市 $2$ 没有设置交易所，但可以通过已铺设的道路 $1$ 到达设置了交易所的城市 $1$。
• 城市 $3$ 设置了交易所。
• 城市 $4$ 没有设置交易所，但可以通过已铺设的道路 $3$ 到达设置了交易所的城市 $1$。
• 城市 $5$ 设置了交易所。
• 城市 $6$ 没有设置交易所，但可以通过已铺设的道路 $7$ 到达设置了交易所的城市 $5$。
• 城市 $7$ 没有设置交易所，但可以通过已铺设的道路 $7$ 和 $8$ 到达设置了交易所的城市 $5$。

因此，总共需要 $40 + 30 + 70 + 40 + 60 + 60 + 50 = 350$ 枚金币。

样例解释 2

在所有城市都设置交易所会更便宜。

由 ChatGPT 4.1 翻译