You are given an undirected weighted graph $$G$$ with $$N$$ nodes and $$M$$ edges. Each edge has a weight assigned to it. You are also given an array $$A$$ of $$N$$ elements. Graph $$G$$ does not contain any self-loops and multiple edges. 

If a new edge is added between node $$u$$ and $$v$$, then the weight of this edge is $$max(A[u], A[v])$$.  

Add some edges (possible 0) until there exists a subgraph $$H$$ such that it satisfies the following conditions:

• $$H$$ contains all the vertices of $$G$$.
• $$H$$ is connected.
• $$H$$ is bipartite.
• $$H$$ does not contain self-loops or multi-edges.
• Number of additional edges should be as minimum as possible.

Find the minimum possible weight of such subgraph $$H$$. The weight of a graph is defined as the summation of weights of all the edges present in the graph.

Note

• A graph is said to be connected if there is a path from any vertex to any other vertex in the graph.
• A graph is called bipartite whose vertices can be divided into two disjoint and independent sets $$U$$ and $$V$$ such that every edge connects a vertex in $$U$$ to one in $$V$$.
• A subgraph $$S$$ of a graph $$G$$ is a graph whose vertex set $$V(S)$$ is a subset of the vertex set $$V(G)$$, that is \(V(S)⊆V(G)\), and whose edge set $$E(S)$$ is a subset of the edge set $$E(G)$$, that is \(E(S)⊆E(G)\).

Input format

• The first line contains a single integer $$T$$ that denotes the number of test cases.
• For each test case:
  • The first line contains an integer $$N$$.
  • The second line contains an integer $$M$$.
  • The third line contains $$N$$ space-separated integers denoting array $$A$$.
  • Next $$M$$ lines contain three space-separated integers $$u v w$$ denoting an edge between nodes $$u$$ and $$v$$ with weight $$w$$.

Output format

For each test case, print the minimum possible weight of subgraph $$H$$. Print the output for each test case in a new line.

Constraints