Problem Description

There are $ N $ towns numbered from $ 1 $ to $ N $. There are $ M $ roads, where the $ i $-th road connects town $ A_i $ and town $ B_i $ bidirectionally, and accumulates $ C_i $ fatigue when traversed.
There is at most one road directly connecting any two towns, and any two towns can be reached by traversing some roads.
Each town has a warp pad of type A, type B, or type C. The configuration of warp pads is given by a string $ S $, where the type of warp pad in town $ i $ is $ S_i $. There may be types of warp pads that do not exist in any town.
Warp can be performed between two towns with different types of warp pads, and the fatigue accumulated during warp is as follows:

• Between towns with type A and type B: $X_{\mathrm{AB}}$
• Between towns with type A and type C: $X_{\mathrm{AC}}$
• Between towns with type B and type C: $X_{\mathrm{BC}}$

Warp cannot be performed between towns with the same type of warp pad.
Find the minimum total fatigue accumulated when traveling from town $ 1 $ to town $ N $ using only roads and warp.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $X_{\mathrm{AB}}$ $X_{\mathrm{AC}}$ $X_{\mathrm{BC}}$ $ S $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ A_3 $ $ B_3 $ $ C_3 $ $\hspace{25pt}\ \vdots$ $ A_M $ $ B_M $ $ C_M $

Output Format

Output the minimum total fatigue accumulated when traveling from town $ 1 $ to town $ N $.

Sample Input and Output

Sample Input #1

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

Sample Output #1

15

Sample Input #2

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

Sample Output #2

20

Sample Input #3

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 #3

8

Notes/Hints

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, 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$
• There is at most one road directly connecting any two towns
• Any two towns can be reached by traversing some roads
• All inputs except $ S $ are integers

Sample Explanation 1

First, warp from town $ 1 $ to town $ 2 $ (from type A to type B), then use the second road to travel from town $ 2 $ to town $ 3 $, accumulating $10\ +\ 5\ =\ 15$ fatigue, which is optimal. Note that direct warp from town $ 1 $ to town $ 3 $ is not possible because both have type A warp pads.

Sample Explanation 2

Warp from town $ 1 $ to town $ 2 $ (from type A to type B), then further warp from town $ 2 $ to town $ 3 $ (from type B to type C), accumulating $10\ +\ 10\ =\ 20$ fatigue, which is optimal. Direct warp from town $ 1 $ to town $ 3 $ is possible but not optimal because it would incur $X_{\mathrm{AC}}\ =\ 1000000000$ fatigue.

见题面 Input 部分

见题面 Output 部分