Bouncing Ball Rounds

This is the hard version of the problem. A ball initially located at point \(0\) on the number line moves in the positive direction. Devices are installed at points \(1,2,\dots,n\) with costs \(a_1,a_2,\dots,a_n\) respectively. When the ball passes through point \(i\), you can pay a cost of \(a_i\) to reverse its moving direction (from rightward to leftward or vice versa).

There are \(m\) conditions. The \(i\)th condition is given in the form "the ball needs to move from point \(x_i\) to point \(y_i\) at least \(k_i\) times", where \(x_i>y_i\). More precisely, the ball’s trajectory should contain the pattern \[ \ldots\to x_i\to\ldots\to y_i\to\ldots\to x_i\to\ldots\to y_i\to\ldots, \] with the segment from \(x_i\) to \(y_i\) occurring at least \(k_i\) times. In each such occurrence, when the ball is moving right and reaches \(x_i\), you may choose to pay \(a_{x_i}\) to reverse its direction (so that it goes left) and then delay any further reversal until after passing \(y_i\) (thus ensuring a leftward travel from \(x_i\) to below \(y_i\)).

Your task is to determine the minimum total cost required to satisfy all these conditions. Note that a valid strategy can perform several round trips: after a bounce at \(x_i\) (with cost \(a_{x_i}\)) and the subsequent reversal at some device \(j\) (with \(j\le y_i\)) costing \(a_j\), the ball will eventually return to \(x_i\) and can start a new round trip if needed. Thus, one round trip to cover a single requirement \((x_i,y_i)\) costs at least \(a_{x_i}+\min_{1\le j\le y_i}{a_j}\).

Input and Output of This Version: This is the hard version of the problem. The full score of this problem is 50 points.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1\le n,m\le 10^5\)).

The second line contains \(n\) integers \(a_1,a_2,\dots,a_n\) (\(1\le a_i\le 10^9\)), where \(a_i\) is the cost of reversing the ball's direction at point \(i\).

Then \(m\) lines follow. Each of these lines contains three integers \(x_i, y_i, k_i\) (with \(1\le y_i<x_i\le n\) and \(1\le k_i\le 10^9\)), representing a condition that requires the ball to move from point \(x_i\) to point \(y_i\) (in one uninterrupted leftward journey) at least \(k_i\) times.

outputFormat

Output a single integer — the minimum total cost needed to satisfy all the conditions.

sample

3 1
3 2 1
3 2 1

3