PRISTOJBA - Pristojba

no tags

In a galaxy far far away there is a new low-cost space carrier starting daily interplanetary flights.
In the galaxy there are N planets, numbered with integers from 1 to N. Cost of a flight between two planets
depends only on take-off/landing fees of those planets. For each planet k you are given his fee, pk, so the cost
of a flight between planets a and b is pa + pb

Space carrier wants to determine the flights it will offer daily so that any planet can be reached from any other planet, directly or indirectly.

Because of space reasons it's possible to conduct flights only between certain pairs of planets.
Allowed flights are described with M permissions of form "xk ak bk" which means it's possible to conduct a bidirectional flight between planet xk and any planet c, where ak ≤ c ≤ bk.

Find the minimum total cost of offered flights such that all planets are connected.

Input

N M
p1 p2 .. pN
x1 a1 b1
x2 a2 b2
..
xM aM bM

1 ≤ N, M ≤ 105
For each pk following holds: 0 ≤ pk ≤ 106.
For each permission it holds that either xk < ak or xk > bk.
Also, it's possible that some pairs of planets are listed in more than one permission.

It will always be possible to choose flights such that all planets are connected.

Output

Minimum daily cost of space carrier transportation system.

Example

```Input:
6 83 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:
46```
`Explanation: we connect following pairs of planets: (1, 3), (1, 4), (4, 2), (2, 5), (2, 6).`

 Added by: Ivan Katanic Date: 2016-04-17 Time limit: 5s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM64 GOSU JS-MONKEY Resource: Croatian IOI Team Selection Test 2016 (G. Matula, I. KataniÄ‡)