Houses and Restaurants

All submissions for this problem are available.
There is a city where people are fond of visiting restaurants. In fact, any building in this town is either a house or a restaurant. There are N buildings in the city and they are conveniently numerated by integer numbers from 1 to N. To move from some building to others there are M twoway roads. Each road connects two buildings. It is possible that there are several roads that connect the same pair of buildings, but there won't be a road that connects a building to itself. Chef wants to make the ways to his restaurants more interesting. To do that he is going to decorate some roads. Each road has its own integer cost of decorating. Some costs may be negative. If the cost is negative Chef will get some reward for decorating this road. Now Chef doesn't have much money so he wants to decorate roads in such a way that from each house, at least one restaurant is reachable using only decorated roads. The total cost of decorated roads should be minimal. So, your task is to help him to calculate the minimal cost of any satisfactory subset. It might be negative if Chef's rewards for decorating some roads are greater than his spent money.
Input
There first line of input contains an integer T  the number of test cases.
Then T test cases follow.
For each test case there will be integers N and M  the number of buildings and the number of roads.
Then a string of N letter follows. Ith symbol of this string is "R" if the corresponding building is a restaurant and "H" if it is a house.
Then there are M lines. Each line consists of three integers  X_{i} Y_{i} Z_{i}. They describe a road that connects buildings X_{i} and Y_{i} with the cost of decorating equal to Z_{i}.
Output
For each test case output the minimal cost of any satisfactory subset of roads.
Constraints
2<=N<=100000
1<=M<=400000
20000<=Z_{i}<=20000
Sum over all N in a single input file will not exceed 200000.
Sum over all M in a single input file will not exceed 400000.
It is guaranteed that you can reach every building from any other building.
There is at least one resturant in the city.
Example
Input: 3 3 5 HHR 1 2 3 1 2 5 1 3 10 3 2 1 3 1 7 2 2 RR 1 2 1 2 1 2 3 3 HRR 1 2 1 1 3 2 2 3 3 Output: 2 0 1
Author:  xcwgf666 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/RHOUSE 
Tags  easy, jan12, xcwgf666 
Date Added:  11112011 
Time Limit:  0.401412 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions