0 Judge
Code: 0
Chuck is a secret agent on a mission in the Northern France. The only way to move from a place to another there is either by walking or driving a car.
There are $V$ villages (numbered from $1$ to $V$) connected by either bi-directional highways or cobblestone roads. It is not permitted to walk on highways since it is too dangerous. Also, driving on cobbled roads is not permitted because the cobblestones were remained untouched in the centuries and therefore could not bear the heavy weight of a car. However, driving on highways or walking on cobblestones is permitted.
To complete the mission, Chuck needs to visit the villages in the exact order of a given list $L$ and some villages might be visited more than once. For example, if the visiting order is A-B-C-B-D, then he'll have to visit the village B twice.
At the beginning of the mission, Chuck will be in the first village listed in $L$ with his car. The car can only be parked in a village. Whenever he wants to drive, he'll have to walk back to the village where the car was parked first.
It is your task to find the shortest possible total time that Chuck needs to spend before the mission is accomplished.
The first line of the input contains an integer $T$ ($1 \leq T \leq 50$), the number of test cases. Each test case is formatted as follows.
$V\;E$
$x_{1}\;y_{1}\;c_{1}\;t_{1}$
$x_{2}\;y_{2}\;c_{2}\;t_{2}$
$\vdots$
$x_{E}\;y_{E}\;c_{E}\;t_{E}$
$K$
$v_{1}\;v_{2}\;\cdots\;v_{K}$
The first line of each test case consists of 2 integers $V$ ($1 \leq V \leq 200$) and $E$ ($1 \leq E \leq 10000$) representing that there are $V$ villages and $E$ roads in the map. Followed by $E$ lines, indicating that the $i^{th}$ road connects village $x_i$, $y_i$ with time $c_i$ ($1 \leq c_i \leq 1000$) needed while $t_i$ is an alphabet either H or C representing highway or cobbled roads, respectively. Note that there could be multiple roads connecting any pair of villages.
In the last 2 lines of each test case is the information about the mission. The first line consists a single integer $K$ ($1 \leq K \leq 1000$), and in the second line, the visit order of $K$ integers $v_{1}$, $v_{2}$, $\cdots$, $v_{K}$ will be listed.
For each test case, output an integer, which denotes the minimum possible time that Chuck needs to spend before the mission is accomplished, in a line.
2
3 3
1 2 5 C
1 2 7 H
2 3 11 H
3
1 2 3
5 5
1 2 15 C
2 3 10 C
4 5 7 C
1 3 30 H
3 4 100 H
5
1 3 5 4 1
18
269
no