Problem Statement

There are $N$ locations numbered from $1$ to $N$ and $M$ roads. Using the $i\;(1\leq i\leq M)$-th road, you can travel from location $U_i$ to location $V_i$ in $C_i$ minutes. You cannot travel along this road in the reverse direction.

You are also given a string $S = S_1S_2\cdots S_N$ of length $N$ consisting of uppercase English letters. At location $i\;(1\leq i\leq N)$, there is $1$ cookie with $S_i$ written on it.

Now, you have an empty string $T$. Starting from location $1$, you may repeat the following action $0$ or more times, choosing one of the options each time.

• If there is a cookie at your current location, eat it. Append the character written on the cookie to the end of $T$.
• Use a road going out of your current location to move to another location.

Determine whether you can make $T=$ KCPC, and if so, output the minimum total time spent using roads.

Input

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

$N$ $M$
$U_1$ $V_1$ $C_1$
$U_2$ $V_2$ $C_2$
$\vdots$
$U_M$ $V_M$ $C_M$
$S$

• $4\leq N\leq 10^5$
• $1\leq M\leq 1.5\times 10^5$
• $1\leq U_i, V_i\leq N\;\;(1\leq i\leq M)$
• $U_i\neq V_i\;\;(1\leq i\leq M)$
• $(U_i,V_i)$ are pairwise distinct
• $1\leq C_i\leq 10^9\;\;(1\leq i\leq M)$
• $N,M,U_i,V_i,C_i$ are integers
• $S$ is a string of length $N$ consisting of uppercase English letters

Output

If you can make $T=$KCPC, output the minimum total time spent using roads on $1$ line.
Otherwise, output -1.
Print a newline at the end.

Sample

4 5
1 2 2
2 3 2
3 1 3
2 4 1
4 2 1
PKCC

10

6 7
1 2 3
2 3 4
3 1 3
3 4 2
4 5 1
5 6 4
6 4 3
CPAKBC

-1

7 8
1 2 4
1 3 3
2 4 2
3 5 5
3 6 2
4 5 1
5 7 4
6 7 2
KKCCPCC

11

15 20
6 15 59680731
4 14 512184729
4 7 928045980
15 12 936533142
5 2 641980757
9 3 154750438
11 6 57032185
15 2 194588886
13 14 631990846
12 5 6215057
2 12 791775040
2 9 476629800
14 5 126298100
10 11 267993404
10 1 73997749
12 8 450877870
1 13 296054234
12 10 182601287
3 4 604956581
1 14 933531002
CCCJCCCCZCCCPCK

5176583842