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
Input  Output 

2 1 1 2 15 aa Copy

15 Copy

3 3 1 2 15 1 3 54 2 3 10 agv Copy

1 Copy
