题目背景

译自 Izborne Pripreme 2016 (Croatian IOI/CEOI Team Selection) 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$ 间有边连接」。

求出这张无向图的最小生成树的边权和。

输入格式

第一行，两个正整数 $n,m$。

第二行，$n$ 个非负整数 $p_1,\cdots,p_n$。

接下来 $m$ 行，每行三个正整数 $x,l,r$。

不保证三元组两两不同，但保证 $x\not\in [l,r]$。

输入数据保证有解。

输出格式

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

4 4
2 4 1 0
1 2 3
1 3 4
3 1 1
4 1 2

9

6 8
3 5 8 2 9 4
3 1 2
6 3 3
3 1 1
6 2 2
2 3 6
3 1 2
3 2 2
4 1 1

46

12 10
9 2 7 5 5 9 3 6 5 7 8 8
6 3 3
9 1 1
6 10 11
1 3 11
5 6 12
3 5 5
12 3 7
6 1 4
4 6 6
10 4 6

126

提示

对于 $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]$；
• 存在一组解。