Celine A.K.A Selen thought she made a mistake when she joined Shadi's team, so Anton and Asem believe that Shady can solve this question to prove her wrong, can he? 

You are given a weighted undirected graph that does not contain loops or multiple edges, with $n$ nodes and $m$ edges, where each node contains a single lowercase letter.

Let's call a path good if:

1. It's a simple path (i.e. each node that lies on the path is visited only once).

2. The string created by this path is a palindrome of length $> 1$.

Find the minimum possible weight of a good path in the graph, or report that no good paths exist.

The first line of input contains $2$ integers $n$ and $m$ ($1 \leq n \leq 10^5; n - 1 \leq m \leq min(\frac{n(n - 1)}{2}, 10^5)$), the number of nodes and edges in the graph, respectively.

The next $m$ lines each contain $3$ integers $a$, $b$ and $w$ ($1 \leq a,b \leq n , a \neq b , 1 \leq w \leq 10^9$), representing an undirected edge between node $a$ and node $b$ with weight $w$.

The last line contains a string of length $n$ consisting of lowercase english letters, where the $i^{th}$ node contains the $i^{th}$ letter of the string.

Output the minimum weight of a good path in the graph, or $-1$ if no good path exists