problem #65 - 선아의 선물

선아의 선물

Time Limit: 1.5 SecMemory Limit: 1024 MiB

Example Input 1

7 8
1 5
H A E U L L E
HAEUL
1 2 1
2 3 1
3 4 1
4 5 10
4 6 1
4 7 1
6 5 2
7 5 1

Example Output 1