Landing Fees

Time limit5sMemory limit1024 MB

Summary

Given planet fees and permits that link a planet to a range of planets, find the minimum total route cost that connects all planets.

Level: Medium6 of 10
Topics: Minimum spanning tree, Union-find, Segment tree
Solved: No attempts yet

Problem

A new budget airline in a distant galaxy is starting interplanetary flights. The galaxy has $n$ planets numbered from 1 to $n$ . The cost of opening a route with daily flights in both directions between planets $a$ and $b$ depends only on the landing and takeoff fees of those two planets. Planet $k$ has fee $p_k$ , so a route between $a$ and $b$ costs $p_a + p_b$ .

Figure 1: The second test case. Each planet node shows its fee. Routes in the optimal choice are drawn in bold.

The airline wants every planet connected, so that any planet can be reached from any other planet directly or through other planets. Routes cannot be opened between any two planets. They can only be opened between certain pairs. The allowed pairs are given by $m$ permits of the form $x_k$ $a_k$ $b_k$ . A permit means that a route can be opened between planet $x_k$ and every planet $c$ with $a_k \le c \le b_k$ .

Find the minimum total cost of opening routes so 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 second line contains $n$ natural numbers $p_1, p_2, \ldots, p_n$ separated by spaces, the fee of each planet. The next $m$ lines describe the permits. The $k$ -th of these lines contains three natural numbers $x_k$ , $a_k$ , and $b_k$ .

The constraints are $0 \le p_k \le 10^6$ , $1 \le x_k \le n$ , and $1 \le a_k \le b_k \le n$ . Also, $x_k$ is never between $a_k$ and $b_k$ , so either $x_k < a_k$ or $b_k < x_k$ . Several permits may have the same parameters, and the same route may appear in several permits. The input always allows all planets to be connected.

Output

Print the minimum possible total cost of opening routes.

Examples3

Example 1
Input
```
4 4
2 4 1 0
1 2 3
1 3 4
3 1 1
4 1 2
```
Expected output
```
9
```

Example 2

Input

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

Expected output

Example 3

Input

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

Expected output