1785. 特殊生成树
时间限制：2000 MS 内存限制：256 MB
题目描述
## 题目描述 给定$n$ 个点，每个点有点权 $a_i$，连结两个点花费的代价为两点的点权和。另外有 $m$ 条特殊边，参数为 $x,y,w$。意为如果你选择这条边，就可以花费 $w$的代价将点 $x$ 和点 $y$ 连结起来，当然你也可以不选择这条边。求使整个图联通的最小代价 ## 输入格式 第一行包含两个整数 $n$ 和$ m（1\len\le2\cdot10^5，0\lem\le2\cdot10^5）$，分别是图中的顶点数和特殊边数。 第二行包含$n$ 个整数 $a_1，a_2，\dots，a_n（1\lea_i\le10^{12}）$—写在顶点上的数字。 然后是 $m$ 行，每行包含三个整数 $x，y$ 和 $w（1\lex，y\len，1\lew\le10^{12}，x\ney）$，表示特殊边：您可以添加一条连接顶点 $x$ 和顶点$y$ 的边， 而这条边缘将花费 $w$ 。 ## 输出格式 打印一个整数--连接该图所需支付的最小花费。 ## 数据范围 ... ## 输入 ```in1 3 2 1 3 3 2 3 5 2 1 1 ``` ## 输出 ```out1 5 ``` ```in2 4 0 1 3 3 7 ``` ```out2 16 ``` ```in3 ... ``` ```out3 ... ``` ## 提示