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, p_k, so the cost of a flight between planets a and b is p_a + p_b. 

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 "x_k a_k b_k" which means it's possible to conduct a bidirectional flight between planet x_k and any planet c, where a_k ≤ c ≤ b_k.

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

Input

N M
p₁ p₂ .. p_N 
x₁ a₁ b₁
x₂ a₂ b₂
..
x_M a_M b_M 

1 ≤ N, M ≤ 10⁵
For each p_k following holds: 0 ≤ p_k ≤ 10⁶.
For each permission it holds that either x_k < a_k or x_k > b_k.
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 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).