Conecte!

Sams está brincando com seu novo grafo com $n$ vértices. Ela quer adicionar arestas não-direcionadas no grafo, que inicialmente não contém nenhuma. Além disso, cada vértice $v$ do
grafo possui um número $a_v$.

No jogo inventado por Sams, o custo de adicionar uma aresta que liga os vértices $u$ e $v$ do grafo é $a_u + a_v$. No entanto, para deixar o jogo mais interessante, ela adicionou $k$ arestas especiais: são arestas que ligam vértices $u$ e $v$ com um custo $w$, independente dos valores $a_u$ e $a_v$. No entanto, não é obrigatório usar o custo de uma aresta especial, ou seja, ainda é possível conectar a aresta $(u, v)$ com custo $a_u + a_v$.

Sams deseja que você responda a seguinte pergunta: qual é o menor custo total necessário para tornar o grafo do jogo conexo?

Entrada

A primeira linha contém dois inteiros $n$ ($1 \leq n \leq 2\cdot 10^5$) e $k$ ($0 \leq k \leq 2\cdot 10^5$), a quantidade de vértices no grafo e a quantidade de arestas especiais, respectivamente.

A segunda linha contém $n$ inteiros: $a_1, a_2, ..., a_n$ ($1 \leq a_i \leq 10^{12}$).

Em seguida, serão dadas $m$ linhas, cada uma com três inteiros, $u$, $v$ ($1 \leq u, v \leq n, u \neq v$) e $w$ ($1 \leq w \leq 10^{12}$), caracterizando as arestas especiais.

Saída

Imprima o menor custo total possível para tornar o grafo conexo.

Exemplo

ENTRADA	SAÍDA
5 4 1 2 3 4 5 1 2 8 1 3 10 1 4 7 1 5 15	18