P11307 [COTS 2016] 建造费 Pristojba

译自 [Izborne Pripreme 2016 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2016/) D2T2。$\texttt{5s,0.5G}$。

有一张 $n$ 个点的简单无向图 $G$。 给定数列 $p$，边 $(i,j)$（$i\neq j$）的边权为 $p_i+p_j$。 然而，不是所有 $i,j$ 间都有边连接。给定 $m$ 个三元组形如 $x,l,r$，表示「$\forall l\le y\le r$，$x,y$ 间有边连接」。 求出这张无向图的[最小生成树](https://www.luogu.com.cn/user/398152)的边权和。

第一行，两个正整数 $n,m$。 第二行，$n$ 个非负整数 $p_1,\cdots,p_n$。 接下来 $m$ 行，每行三个正整数 $x,l,r$。 **不保证三元组两两不同**，但保证 $x\not\in [l,r]$。 **输入数据保证有解。**

输出一行一个整数，表示答案。

对于 $100\%$ 的数据，保证： - $1\le n,m\le 10^5$； - $0\le p_i\le 10^6$； - $1\le x\le n$； - $1\le l\le r\le n$，$x\not\in [l,r]$； - 存在一组解。 | 子任务编号 | $n,m\le $ | 得分 | | :--: | :--: | :--: | | $ 1 $ | $ 10^3$ | $ 20 $ | | $ 2 $ | $ 10^5 $ | $ 80 $ |