题目内容

要在 $p$ 个站点之间建成一张可互相传输的光纤骨干网（即全部站点连通）。

站点之间已有 $q$ 条双向预埋管道。建网手段有两种，可混合使用：

1. 启用管道：对已有管道，花费代价 $z$ 将其启用为光纤干线；启用后两端站点即可互通。
2. 设立枢纽：在站点 $i$ 设立枢纽，花费为 $f_i$。所有设立了枢纽的站点，会经由平台专用空中光链路两两互通，因而在骨干网中视为已连通。

骨干网中至少要有一个枢纽；当 $p=1$ 时也必须设立。

请计算：让全部站点互相可达所需的最小总花费。

输入描述

第一行一个整数 $p$（$1\le p\le 10^5$），表示站点个数。

第二行一个整数 $q$（$0\le q\le 2\times 10^5$），表示预埋管道条数。

第三行 $p$ 个整数 $f_1,f_2,\dots,f_p$（$1\le f_i\le 10^9$），表示各站设立枢纽的花费。

随后给出 $q$ 条管道，每条占一行，含三个整数 $x,y,z$（$1\le x,y\le p$，$x\neq y$，$1\le z\le 10^9$），依次为端点与启用代价。保证无重边。

输出描述

输出一个整数，表示最小总花费。

样例1

输入

4
3
50 50 50 10
1 2 10
2 3 10
3 4 100

输出

80

说明

启用管道 $1{-}2$、$2{-}3$（各花费 $10$），并在站点 $1$（或 $2$、$3$）与站点 $4$ 各设一个枢纽（花费 $50+10$），总花费 $80$。

样例2

输入

3
2
100 20 30
1 2 5
2 3 50

输出

55

说明

启用 $1{-}2$（花费 $5$），在站点 $2$、$3$ 设立枢纽（花费 $20+30$），总花费 $55$。