Подарок Диппера

Во время очередного приключения Диппер нашел строку $s$ длинны $n$. Он считает, что эта строка является идеальным подарком для Мэйбл. Она привередливая, поэтому не каждая строка ей понравится. К счастью, у Диппера есть знакомый мастер, который умеет изменять строки за определенное количество монет.

Мальчик хочет угодить Мейбл и сделать строку, которая ей понравится, потратив минимальное количество монет. Мастер имеет каталог из $m$ операций замены. Каждая операция позволяет заменить определенный символ $a$ в любой позиции строки на символ $b$, заплатив $c$ монет. Любую операцию можно использовать неограниченное количество раз в любой позиции строки. Мастер может заменять символы, которые он сам раньше ставил на эту позицию. В каталоге мастера может быть несколько операций изменение $a$ на $b$ с разными стоимостями.

Строка называется $k$-строкой, если она может быть представлена в виде $k$ копий некоторой строки, записанных подряд. Например, строка <<aabaabaabaab>> является одновременно $1$-строкой, $2$-строкой и $4$-строкой, но не является $3$-строкой, $5$-строкой, $6$-строкой и так далее. Назовем строку <<красивой>>, если она является $k$-строкой, для $k$ больше единицы. Мейбл нравятся только красивые строки. Помогите Дипперу понять, может ли он получить красивую строку, а если может, то какое минимальное количество монет ему необходимо потратить на работу мастера.

В первой строке заданы числа $n$ и $m$ --- длина строки $s$ и количество операций ($2 \le n \le 10^5$; $1 \le m \le 10^5$).

Во второй строке задана последовательность маленьких латинских букв длины $n$ --- строка $s$.

Далее следует $m$ строк. В каждой записаны две маленькие латинские буквы $a$, $b$ и число $c$ --- операция, которая соответствует замене символа $a$ на $b$ за цену $c$ ($0 \le c \le 100\\,000$).

Если не существует способа сделать строку $s$ красивой, то выведите -1, иначе выведите количество монет, которое нужно потратить.

abcdba $\to$ dbcdba $\to$ dbcdbz $\to$ dbcdbc

1. Заменяем букву a на d, заплатив 1.
2. Заменяем букву a на z, заплатив 3.
3. Заменяем букву z на c, заплатив 2.

Ответ: 1 + 3 + 2 = 6

Строка dbcdbc является 2-строкой.