Minimum Cost to Ensure Connectivity

You are given an undirected weighted graph with n nodes and m edges. Each node is designated as either a warehouse (W) or a customer (C). Your goal is to choose a subset of the edges such that:

• The graph becomes connected (i.e. there is a unique spanning tree connecting all nodes).
• At least one warehouse and one customer lie in the same connected component (i.e. there is at least one path between a warehouse and a customer).

You should compute the minimum total cost of such a spanning tree. Formally, if the chosen edges form a spanning tree, the cost is given by:

$\text{cost} = \sum_{e \in \text{spanning tree}} w_e$

If no such spanning tree exists, output -1.

Note: The input is given via standard input and the output should be printed to standard output.

inputFormat

The input consists of multiple test cases. The first line contains an integer T representing the number of test cases. Each test case is described as follows:

1. The first line of each test case contains two integers n and m ($1 \le n \le 10^5$, $0 \le m \le 10^5$), where n is the number of nodes and m is the number of edges.
2. The second line contains n space-separated tokens. Each token is either W (warehouse) or C (customer), indicating the type of the corresponding node.
3. The next m lines each contain three integers u v w ($1 \le u,v \le n$, $1 \le w \le 10^9$) representing an undirected edge between nodes u and v with weight w.

outputFormat

For each test case, output a single line containing one integer: the minimum total cost to ensure connectivity under the given conditions, or -1 if it is impossible.

## sample

5
6 7
W C C W C W
1 2 10
2 3 15
3 4 10
4 5 15
3 5 10
5 6 5
1 6 20
4 4
W C C W
1 2 10
2 3 10
3 4 10
4 1 10
3 0
W C W
5 6
W C C C W
1 2 1
2 3 1
3 4 1
4 5 1
1 3 2
3 5 2
5 4
W W C C C
1 2 1
2 3 2
2 4 3
4 5 4

50
30
-1
4
10

</p>