The first line of the input gives the number of test cases, $T \; (1 \le T \le 100)$. $T$ test cases follow.
For each test case, the first line contains five integers $n, m, s, t, x \; (1 \le n \le 10^5, \; 1 \le m \le 2 \times 10^5, \; 1 \le x \le 10^9)$, representing the number of villages, the number of roads, the bakery's location, home's location, and the time spent for each switching.
The next line contains a string of length $n$, describing the type of each village. The $i^\mathrm{th}$ character is either $\text{L}$ representing village $i$ is LEFT, or $\text{M}$ representing MIDDLE, or $\text{R}$ representing RIGHT.
Finally, $m$ lines follow, the $i^\mathrm{th}$ of which contains three integers $a_i, b_i, d_i \; (1 \le d_i \le 10^9)$, denoting a road connecting village $a_i$ and $b_i$ of length $d_i$.
It is guaranteed that $t$ can be reached from $s$.
The sum of $n$ in all test cases doesn't exceed $2 \times 10^5$. The sum of $m$ doesn't exceed $4 \times 10^5$.