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