Keep it energized

A console maker is building Adventures of Captain Mikado, the game that ships with its new machine. The game has $N$ levels numbered $1$ through $N$, and level $i$ costs exactly $E_i$ units of energy to clear. That is, the player's energy when level $i$ starts must be at least $E_i$, and clearing the level drops the energy by exactly $E_i$. Winning means clearing every level in increasing order, from level $1$ to level $N$, without ever going back to a level that is already cleared.

The player starts with energy $0$. Energy comes from energy packs sold by the $M$ shops scattered across the levels. Each shop sells one kind of energy pack, with a strength $S$ and a cost $C$. The player can buy an energy pack only from a shop on the level he is currently on, and only before starting that level. Buying a pack of strength $S$ sets the energy to $S$ at once, whatever it was just before.

Find the smallest amount of in-game cash that clears all $N$ levels.

The first line contains the number of levels $N$ and the number of shops $M$ ($1 \le N, M \le 10^5$).

The second line contains $N$ integers $E_1, E_2, \dots, E_N$, where $E_i$ is the energy needed to clear level $i$ ($1 \le E_i \le 10^4$).

Each of the next $M$ lines describes one shop with the integers $L$, $S$ and $C$. $L$ is the level the shop is on, and $S$ and $C$ are the strength and the cost of the energy pack it sells ($1 \le L \le N$, $1 \le S \le 10^9$, $1 \le C \le 10^4$).

Print on one line the minimum amount of in-game cash needed to clear all $N$ levels. If clearing every level is impossible, print -1.