Warning

Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

There are $N$ towns numbered $1$ through $N$, and $M$ roads. The $i$-th road connects Town $A_i$ and Town $B_i$ bidirectionally, and you get $C_i$ points of fatigue when you pass through that road. For every pair of towns, there is at most one road that directly connects those towns, and it is possible to travel between those towns by traversing some roads. Additionally, each town has a teleporter of type A, type B, or type C. The placement of teleporters is given to you by a string $S$; the teleporter in Town $i$ is of type $S_i$. There may be some types of teleporters that do not exist in any towns. You can teleport between two towns with different types of teleporters. When you do so, you get the following points of fatigue:

• $X_{\mathrm{AB}}$ points when teleporting between towns with teleporters of type A and type B;
• $X_{\mathrm{AC}}$ points when teleporting between towns with teleporters of type A and type C;
• $X_{\mathrm{BC}}$ points when teleporting between towns with teleporters of type B and type C.

You cannot teleport between towns with the same type of teleporter. Find the minimum possible total points of fatigue you get when going from Town $1$ to Town $N$ only using roads and teleporters.

Constraints

• $2 \le N \le 10^5$
• $1 \le M \le 10^5$
• $1 \le X_{\mathrm{AB}}, X_{\mathrm{AC}}, X_{\mathrm{BC}} \le 10^9$
• $S$ is a string of length $N$ consisting of A, B, and C.
• $1 \le A_i \le N$
• $1 \le B_i \le N$
• $A_i \neq B_i$
• $1 \le C_i \le 10^9$
• For every pair of towns, there is at most one road that directly connects those towns.
• For every pair of towns, it is possible to travel between those towns by traversing some roads.
• All values in input, except $S$, are integers.

Sample Input 1Copy

3 2
10 10 10
ABA
1 2 15
2 3 5

Sample Output 1Copy

15

If you first teleport from Town $1$ (type A) to Town $2$ (type B) and then use the $2$-nd road to go from Town $2$ to Town $3$, you get $10 + 5 = 15$ points of fatigue, which is optimal. Note that both Town $1$ and Town $3$ have a teleporter of type A, so you cannot directly teleport between them.

Sample Input 2Copy

3 2
10 1000000000 10
ABC
1 2 1000000000
2 3 1000000000

Sample Output 2Copy

20

If you first teleport from Town $1$ (type A) to Town $2$ (type B) and from Town $2$ (type B) to Town $C$ (type C), you will get $10 + 10 = 20$ points of fatigue, which is optimal. Note that you can teleport from Town $1$ to Town $3$ directly this time, but it is not optimal since teleporting from a teleporter of type A to that of type C costs $X_{\mathrm{AC}} = 1000000000$ points of fatigue.

Sample Input 3Copy

5 6
5 10 15
ABCBC
5 4 4
3 5 2
1 3 7
3 4 1
4 2 1
2 3 3

Sample Output 3Copy

8