In a distant galaxy, a new low-budget space carrier is starting interplanetary flights. The galaxy contains $n$ planets labeled with numbers from $1$ to $n$. The cost of establishing a new route — daily flights in both directions — between two planets depends only on the takeoff/landing fees of those planets. Specifically, for each planet $k$, its fee $p_k$ is known, and the cost of establishing a new route between planets $a$ and $b$ is equal to $p_a + p_b$.

Figure 1: Illustration of the second test case example. Inside the node representing a planet, its fee is written. The routes in the optimal selection are bolded.

The new carrier wants to establish routes such that all planets are connected, meaning it is possible to travel from every planet to every other planet, either directly or indirectly. However, it is not permitted to establish routes between any two arbitrary planets, but only between certain pairs. The permitted routes are described by $m$ permits of the form "$x_k$ $a_k$ $b_k$", where $x_k, a_k,$ and $b_k$ are planet labels. This permit means that it is possible to establish routes between planet $x_k$ and every planet $c$ for which $a_k \le c \le b_k$ holds.

Determine the minimum possible total cost of establishing routes such that all planets are connected.

Input

The first line contains natural numbers $n$ and $m$ — the number of planets and the number of permits. The next line contains $n$ natural numbers $p_1, p_2, \dots, p_n$ separated by spaces — the fees of the individual planets. For each planet $k$, $0 \le p_k \le 10^6$ holds.

Following this are $m$ lines, where the $k$-th of these $m$ lines contains three natural numbers $x_k, a_k,$ and $b_k$ — the description of the $k$-th permit as described in the problem statement. For each permit, $1 \le x_k \le n$ and $1 \le a_k \le b_k \le n$ hold, and $x_k$ is not located between $a_k$ and $b_k$ (i.e., either $x_k < a_k$ or $b_k < x_k$). It is allowed for some or all parameters to be the same in different permits, and it is also allowed for a single route to appear in multiple different permits.

The input data is such that it is always possible to establish routes so that all planets are connected.

Output

Print the required minimum possible cost.

Subtasks

Examples

Input 1

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

Output 1

9

Input 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

Output 2

46

Input 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

Output 3

126