问题

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

这个国家有 $N$ 个城市和 $M$ 条道路。每条道路直接连接两个不同的城市，道路上没有其他城市。而且，对于任意的两个城市，连接它们的道路最多只有一条。

最开始，所有的道路都没有铺设，每个城市也没有设置交易所。

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

对于任意的城市，如果满足以下条件之一，国家就被称为“良好状态”。

• 对于该城市，已经建设了交易所。
• 对于该城市，虽然没有建设交易所，但通过铺设的道路从该城市可以到达另一个建设了交易所的城市。

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

因为高桥君没有太多金币，所以希望尽量减少实现“良好状态”所需的金币数量。

请编写程序来计算所需金币的最小值。

输入

输入从标准输入读取，其格式如下。

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

• 第 $1$ 行包含两个整数 $N (2 ≦ N ≦ 100,000)$ 和 $M (1 ≦ M ≦ 200,000)$，用空格分隔。表示一共有 $N$ 个城市和 $M$ 条道路。
• 第 $2$ 行到第 $N$ 行是整数 $c_i (1 ≦ c_i ≦ 1,000,000,000)$，用于表示在城市 $i$ 上建设交易所需要的金币数量。
• 第 $N+2$ 行到第 $M+1$ 行是 $3$ 个整数 $a_i$、$b_i$、$r_i (1 ≦ a_i ＜ b_i ≦ N)$，用空格分隔。表示第 $i$ 条道路连接城市 $a_i$ 和城市 $b_i$，铺设道路需要 $r_i$ 枚金币。

部分分

本问题设有部分分。

• 对于满足条件 $N ≦ 8$ 和 $M ≦ 10$ 的数据集 $1$，如果得出了正确的答案，则可以获得 $10$ 分。
• 对于满足条件 $N ≦ 12$ 和 $M ≦ 66$ 的数据集 $2$，除了上述以外，还可以获得额外的 $20$ 分。
• 对于满足条件 $N ≦ 3,000$ 和 $M ≦ 6,000$ 的数据集 $3$，除了上述以外，还可以获得额外的 $30$ 分。
• 对于没有附加限制的数据集 $4$，除了上述以外，还可以获得额外的 $40$ 分。

输出

请输出作为实现“良好状态”所需的最小金币数量。在输出末尾要包含换行符。

示例1

7 8
40
50
30
70
70
80
80
1 2 40
1 3 50
1 4 60
2 5 90
3 4 80
4 5 110
5 6 60
6 7 50

示例1输出

350

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

按照以下条件设置交易所并铺设道路。

• 在城市 $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$ 建立了交易