405883: GYM102152 A On the Road to Happiness

Mr. AH got his special name from his favorite game, which is called On the Road to Happiness. This game is played with a string s consisting of n uppercase English letters, b beautiful cards, and a magical wand.

A beautiful card 'x y c' can be used to swap the letters in positions x and y after paying c coins. Mr. AH can use every beautiful card infinitely, but he must pay each time he wants to use it.

Some of the beautiful cards are interesting, a beautiful card 'x y c' is said to be interesting if Mr. AH cannot move the letter in position x to position y (or the letter in position y to position x) using any sequence of cards unless this card is among them.

The magical wand allows Mr. AH to use the beautiful cards without paying anything, except for the interesting cards, Mr. AH must respect these cards and pay for using them. Mr. AH can use the wand as much as he needs.

A position in the given string is said to be happy if it initially contains the letter 'A'. The goal of the game is to find the minimum cost to move all letters 'H' in the string to the happy positions, such that each happy position can contain at most one 'H' letter.

Mr. AH thinks that he is the king of this game, but he wants to see other players play it to prove that. So Mr. AH asked you to play the game, can you?

The first line contains a single integer T (1 ≤ T ≤ 100) specifying the number of test cases.

The first line of each test case contains two integers n and b (1 ≤ n ≤ 10⁵, 0 ≤ b ≤ 2 × 10⁵), in which n is the length of the string and b is the number of the beautiful cards.

The second line of the each test case contains a string s of length n, consisting of uppercase English letters.

Then b lines follow, each line contains three integers x, y and c (1 ≤ x, y ≤ n, x ≠ y, 1 ≤ c ≤ 100), giving the beautiful cards. It is guaranteed that for each two positions x and y, there is at most one card that can swap the letters in them.

The number of happy positions is between 0 and (inclusive), and it always equals the number of positions that contain the letter 'H'.

It is guaranteed that you can move any letter from its position to any other position.

For each test case, print a single line containing the minimum cost to move all letters 'H' in the string to the happy positions. It is guaranteed that the answer always exists.

2
4 3
HZXA
1 2 5
2 3 2
3 4 3
8 9
HDHBZAZA
1 2 5
1 3 4
2 4 6
3 4 1
4 5 7
5 6 9
5 7 2
6 8 12
7 8 2

10
14

In the second test case, the only interesting beautiful card is '4 5 7', and the letters can be moved by using two sequences of beautiful cards:

• '1 2 5', '2 4 6', '4 5 7', '5 7 2', '7 8 2'
• '1 2 5', '2 4 6', '4 5 7', '5 6 9'

The magic wand will be used on all cards except for the only interesting card, which will be used twice leading to a total cost of 14.