디퍼의 선물

디퍼가 모험 중에 길이가 $n$인 문자열 $s$를 발견했다. 디퍼는 이 문자열이 메이블에게 딱 맞는 선물이라고 생각한다. 메이블은 까다로워서 아무 문자열이나 좋아하지 않는다. 다행히 디퍼에게는 일정한 코인을 받고 문자열을 바꿔 주는 장인 친구가 있다.

디퍼는 최소한의 코인으로 메이블이 좋아할 문자열을 만들려고 한다. 장인에게는 $m$개의 교체 연산 목록이 있다. 각 연산은 문자열의 임의의 위치에 있는 문자 $a$를 문자 $b$로 바꾸며, 비용은 $c$코인이다. 각 연산은 위치에 관계없이 횟수 제한 없이 사용할 수 있다. 장인은 자신이 앞서 넣은 문자도 다시 바꿀 수 있다. 같은 $a$에서 $b$로 바뀌는 연산이 비용만 다르게 여러 개 있을 수도 있다.

문자열이 같은 문자열을 $k$번 이어 붙인 것으로 표현되면 $k$-문자열이라고 한다. 예를 들어 aabaabaabaab는 1-문자열, 2-문자열, 4-문자열이지만 3-문자열, 5-문자열, 6-문자열은 아니다. $k$가 1보다 큰 $k$-문자열을 아름다운 문자열이라고 한다. 메이블은 아름다운 문자열만 좋아한다. 디퍼가 아름다운 문자열을 만들 수 있는지 판단하고, 만들 수 있다면 장인에게 지불해야 하는 최소 코인 수를 구하라.

첫 줄에 문자열 길이 $n$과 연산 개수 $m$이 주어진다 ($2 \le n \le 10^5$, $1 \le m \le 10^5$). 둘째 줄에는 길이 $n$의 소문자 라틴 문자열 $s$가 주어진다. 이어서 $m$개의 줄에 소문자 $a$, $b$와 정수 $c$가 주어지며, 이는 문자 $a$를 $c$코인에 $b$로 바꾸는 연산이다 ($0 \le c \le 100\,000$).

아름다운 문자열을 만들 수 없으면 -1을 출력한다. 그렇지 않으면 필요한 최소 코인 수를 출력한다.

abcdba → dbcdba → dbcdbz → dbcdbc

1. 문자 a를 d로 바꾸며 1코인을 낸다.
2. 문자 a를 z로 바꾸며 3코인을 낸다.
3. 문자 z를 c로 바꾸며 2코인을 낸다.

합계는 1 + 3 + 2 = 6이다. dbcdbc는 2-문자열이다.