在一个遥远的星系中，一家新的廉价太空航空公司正在开启行星际航线。 星系中共有 $n$ 个行星，编号为 $1$ 到 $n$。 在两个行星之间建立一条新航线（双向每日航班）的成本仅取决于这两个行星的起降费。 具体来说，对于每个行星 $k$，已知其起降费为 $p_k$，在行星 $a$ 和 $b$之间建立新航线的成本为 $p_a + p_b$。

图 1：第二个样例测试数据的插图。代表行星的节点内部写有其费用。最优选择中的路线已加粗。

这家新的航空公司希望建立航线，使得所有行星都是连通的，即可以从任意一个行星直接或间接地到达其他任何行星。 然而，并不允许在任意两个行星之间建立航线，而只能在某些特定的行星对之间建立。 允许的航线通过 $m$ 个许可证来描述，格式为 "$x_k\ a_k\ b_k$"，其中 $x_k, a_k, b_k$ 是行星的编号。 该许可证意味着可以在行星 $x_k$ 与满足 $a_k \le c \le b_k$ 的任意行星 $c$ 之间建立航线。

请确定建立航线以使所有行星连通的最小可能总成本。

输入格式

第一行包含正整数 $n$ 和 $m$ — 行星的数量 and 许可证的数量。

第二行包含 $n$ 个由空格隔开的非负整数 $p_1, p_2, \dots, p_n$ — 各个行星的起降费。对于每个行星 $k$，满足 $0 \le p_k \le 10^6$。

接下来的 $m$ 行中，第 $k$ 行包含三个正整数 $x_k, a_k$ 和 $b_k$ — 如题目描述中所述的第 $k$ 个许可证。对于每个许可证，满足 $1 \le x_k \le n$ 且 $1 \le a_k \le b_k \le n$，并且 $x_k$ 不在 $a_k$ 和 $b_k$ 之间（即满足 $x_k < a_k$ 或 $b_k < x_k$）。允许不同的许可证具有部分或全部相同的参数，也允许同一条航线出现在多个不同的许可证中。

输入数据保证总是可以建立航线使得所有行星连通。

输出格式

输出要求的最小可能总成本。

子任务

样例

输入格式 1

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

输出格式 1

9

输入格式 2

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

输出格式 2

46

输入格式 3

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

输出格式 3

126