# Clinic Connectivity
## Problem Statement
Gotham is in dire need of medical infrastructure. The city consists of $N$ blocks, and there are $M$ potential roads that can be repaired to connect these blocks. To ensure every block has access to medical care, clinics must be established.
For each block $i$ ($1 \le i \le N$), there is a specific cost $C_i$ to build a clinic in that block.
For each potential road connecting blocks $x$ and $y$, there is a specific cost $R_{xy}$ to repair it.
The objective is to minimize the total cost such that every block in the city has access to at least one clinic. A block $j$ is considered to have access to a clinic if either:
1. A clinic is built in block $j$.
2. Block $j$ has a path to some block $k$ (where a clinic is built) consisting entirely of repaired roads.
Your task is to find the minimum total cost to satisfy this condition.
## Input Format
The first line contains an integer $T$ ($1 \le T \le 10$), denoting the number of test cases.
For each test case:
- The first line contains two space-separated integers $N$ ($1 \le N \le 10^5$) and $M$ ($0 \le M \le 10^5$), representing the number of blocks and the number of potential roads, respectively.
- The second line contains $N$ space-separated integers $C_1, C_2, \dots, C_N$ ($0 \le C_i \le 10^9$), where $C_i$ is the cost to build a clinic in block $i$.
- The next $M$ lines each contain three space-separated integers $x, y, R_{xy}$ ($1 \le x, y \le N, x \ne y, 0 \le R_{xy} \le 10^9$), denoting an undirected road connection between block $x$ and block $y$ with a repair cost of $R_{xy}$.
## Output Format
For each test case, output a single integer on a new line: the minimum total cost to ensure all blocks have clinic access.
## Sample Test Cases
### Sample Input 1
```
1
5 4
3 3 3 3 3
1 2 2
2 3 2
3 1 2
4 5 2
```
### Sample Output 1
```
12
```
## Constraints
- $1 \le T \le 10$
- $1 \le N \le 10^5$
- $0 \le M \le 10^5$
- $1 \le x, y \le N$, $x \ne y$
- $0 \le C_i \le 10^9$
- $0 \le R_{xy} \le 10^9$
- Time limit: 1 second
- Memory limit: 256 MB
## Explanation
For the given sample, we have $N=5$ blocks and $M=4$ potential roads. The cost to build a clinic in any block is $C_i=3$, and the cost to repair any road is $R_{xy}=2$.
We can model this problem as finding a Minimum Spanning Tree (MST) on a modified graph. Create a virtual "clinic source" node, let's call it node $0$.
- Add an edge from node $0$ to each block $i$ (for $1 \le i \le N$) with weight $C_i$. These edges represent the option of building a clinic in block $i$.
- For each given potential road between blocks $x$ and $y$ with repair cost $R_{xy}$, add an edge $(x, y)$ with weight $R_{xy}$. These edges represent the option of repairing a road.
The goal is to connect all blocks $1, \dots, N$ to the virtual clinic source node $0$ (directly or indirectly) with minimum total cost. This is exactly what an MST algorithm on this new graph (with $N+1$ nodes and $N+M$ edges) would achieve.
Applying Kruskal's algorithm:
The edges are:
- $(0,1)$ cost 3, $(0,2)$ cost 3, $(0,3)$ cost 3, $(0,4)$ cost 3, $(0,5)$ cost 3
- $(1,2)$ cost 2, $(2,3)$ cost 2, $(3,1)$ cost 2, $(4,5)$ cost 2
Sorted edges by weight:
1. $(1,2)$ cost 2
2. $(2,3)$ cost 2
3. $(3,1)$ cost 2
4. $(4,5)$ cost 2
5. $(0,1)$ cost 3
6. $(0,2)$ cost 3
7. $(0,3)$ cost 3
8. $(0,4)$ cost 3
9. $(0,5)$ cost 3
Processing with DSU:
- Initially, each node $0, \dots, 5$ is in its own set. Total cost = 0.
- Consider edge $(1,2)$ cost 2: Union(1,2). Cost += 2. Sets: $\{0\}, \{1,2\}, \{3\}, \{4\}, \{5\}$.
- Consider edge $(2,3)$ cost 2: Union(2,3). Cost += 2. Sets: $\{0\}, \{1,2,3\}, \{4\}, \{5\}$.
- Consider edge $(3,1)$ cost 2: $1$ and $3$ are already connected. Skip.
- Consider edge $(4,5)$ cost 2: Union(4,5). Cost += 2. Sets: $\{0\}, \{1,2,3\}, \{4,5\}$.
- Consider edge $(0,1)$ cost 3: Union(0,1). Cost += 3. Sets: $\{0,1,2,3\}, \{4,5\}$.
- Consider edge $(0,2)$ cost 3: $0$ and $2$ are already connected. Skip.
- Consider edge $(0,3)$ cost 3: $0$ and $3$ are already connected. Skip.
- Consider edge $(0,4)$ cost 3: Union(0,4). Cost += 3. Sets: $\{0,1,2,3,4,5\}$.
- Consider edge $(0,5)$ cost 3: $0$ and $5$ are already connected. Skip.
All blocks are now connected to node $0$. The total minimum cost is $2+2+2+3+3 = 12$.
Loading problem statement...