Minimum Spanning Tree with Special Edge Groups

Given a simple undirected graph \(G\) with \(n\) vertices. Each vertex \(i\) has an associated value \(p_i\). For every two distinct vertices \(i\) and \(j\), if an edge exists then its weight is defined as \(p_i + p_j\). Initially, not all pairs of vertices are connected by an edge. You are given \(m\) triples of the form \(x, l, r\), which means that for all vertices \(y\) satisfying \(l \le y \le r\), there is an edge between vertex \(x\) and vertex \(y\) (note that self-loops are ignored).

Your task is to compute the sum of the edge weights in the minimum spanning tree (MST) of \(G\). The weight of any edge connecting vertices \(i\) and \(j\) (\(i \neq j\)) is given by:

[ w(i,j) = p_i + p_j ]

You may assume that the input guarantees the graph is connected and that duplicate edges (caused by overlapping triples) have the same weight.

inputFormat

The first line contains two integers \(n\) and \(m\) — the number of vertices and the number of triples.

The second line contains \(n\) integers \(p_1, p_2, \ldots, p_n\) where \(p_i\) is the value associated with vertex \(i\).

Each of the following \(m\) lines contains three integers \(x, l, r\), indicating that for every vertex \(y\) with \(l \le y \le r\) (and \(y \neq x\)), there is an edge between vertex \(x\) and vertex \(y\).

outputFormat

Output a single integer representing the total weight of the edges in the minimum spanning tree of the graph.

sample

4 2
1 2 3 4
1 2 3
3 2 4

14