## PRISTOJBA - Pristojba

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**and any planet

_{k}**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_{1} p_{2} .. p_{N}

x_{1} a_{1} b_{1}x_{2} a_{2} b_{2}

..

x_{M} a_{M} b_{M}

1 ≤ N, M ≤ 10^{5}

For each p_{k} following holds: 0 ≤ p_{k} ≤ 10^{6}.

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 1Output: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Ä‡) |