Tạo xâu lũy thừa [powstrm]

Một xâu được gọi là xâu lũy thừa nếu nó là nối liên tiếp nhiều hơn một lần một xâu nào đó, chẳng hạn 'abcabc', 'aaaaa' là các xâu lũy thừa còn 'abcab', 'abac' thì không.

Cho xâu S độ dài N chỉ gồm các chữ cái latin in thường và M phép biến đổi kí tự trong xâu, mỗi phép biến đổi có dạng: đổi một kí tự a nào đó trong xâu thành kí tự b với chi phí c. Có thể áp dụng các phép biến đổi với số lần tùy ý, kể cả đối với kí tự là kết quả của biến đổi trước đó.

Hãy xác định tổng chi phí nhỏ nhất để biến đổi xâu S thành một xâu lũy thừa.

Dữ liệu

Dòng 1: hai số nguyên N,M (2≤N≤10^5;1≤M≤10^5);

Dòng 2: xâu S;

Dòng 3…M+2: mỗi dòng mô tả một phép biến đổi: kí tự a, kí tự b, số nguyên c (0≤c≤10^5).

Kết quả

Dòng 1: số nguyên là tổng chi phí biến đổi nhỏ nhất.

Ví dụ

abcdba  →  dbcdba  →  dbcdbz  →  dbcdbc