J. Jinglebell
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

It's Christmas Eve! Santa Claus takes a quick trip in his time machine to visit his good friend, Doraemon, in the 22nd century. Seeing Santa so busy, Doraemon offers to help with a futuristic sleigh and some amazing gadgets!

This year, they are delivering two special items:

  • Yummy Dorayaki for the good kids (like Nobita and Shizuka).
  • A special "Reflection Mirror" gadget for the naughty kids (like Gian) to help them see their mistakes.

But Doraemon has a strict rule from his "Future Gadget Rulebook" to make sure the deliveries are perfect:

  • The wonderful, sweet smell of Dorayaki can't be ruined by passing through a naughty kid's house.
  • The special power of the Reflection Mirror will get weak if it passes through a good kid's house.

So, for each delivery, Santa must travel from Doraemon's workshop to one kid's house and come straight back to the workshop to pick up the next item. Your job is to help Santa and Doraemon find the shortest total distance they need to travel to deliver everything correctly.

You are given a map with Doraemon's workshop and all the kids' houses. The roads connect these places, and each road has a certain length. Every house is either a "Good Kid" house or a "Bad Kid" house.

Santa has to make one trip for each and every house:

  • Start at the workshop.
  • Travel to one house to deliver an item.
  • Travel all the way back to the workshop.

Here are the two very important rules for the path from the workshop to the house, and from the house back to the workshop:

  • When delivering Dorayaki to a Good Kid, the path cannot go through any Bad Kid's house.
  • When delivering a Reflection Mirror to a Bad Kid, the path cannot go through any Good Kid's house.

You are guaranteed that Santa can always find a way to reach every house by following these rules.

Input

The first line has one number, $$$n$$$ ($$$1 \le n \le 10^5$$$), which is how many houses there are.

The second line has a string of $$$n$$$ letters. Each letter tells you the type of a house. 'G' is for a Good kid's house, and 'B' is for a Bad kid's house.

The third line has one number, $$$m$$$ ($$$1 \le m \le 3 \cdot 10^5$$$), which is how many roads there are on the map.

The next $$$m$$$ lines describe the roads. Each line has three numbers: $$$u$$$, $$$v$$$, and $$$d$$$ ($$$0 \le u,v \le n, 1 \le d \le 10^6$$$). This means there is a road between place $$$u$$$ and place $$$v$$$ with a distance of $$$d$$$. Place $$$0$$$ is Doraemon's workshop, and places $$$1$$$ to $$$n$$$ are the houses.

Output

Print one single number — the shortest total distance Santa must travel for all the deliveries combined.

Example
Input
3
GBG
4
0 1 10
0 2 12
1 3 5
2 3 6
Output
74