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.


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.


Minimum daily cost of space carrier transportation system.


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

Added by:Ivan Katanic
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ć)