문제

개의 마을과 개의 두 마을을 연결하는 도로가 있다. 선아는 친구를 만나기 위해 마을 에서 시작해서 마을 로 가려고 한다. 각 마을에는 영어 대문자 알파벳 중 하나가 적힌 열쇠고리를 팔고 있는데 선아는 친구를 위해 기념품으로 친구의 이름에 포함된 글자들을 모아서 선물하려고 한다. 선아의 친구의 이름은 서로 다른 영어 알파벳 다섯 개로 이루어진 문자열이다. 각 마을에서 판매하는 열쇠고리의 종류와 마을들 사이의 연결 상태가 주어졌을 때 선아가 다섯 종류의 열쇠고리를 모두 모아서 마을 에서 마을 로 갈수 있는 최단 경로의 길이를 찾아주자.

입력

입력의 첫째 줄에는 마을의 개수 와 도로의 개수 가 공백으로 구분 지어 주어진다.

두 번째 줄에는 선아가 시작하는 마을의 번호 와 도착하고자 하는 마을의 번호 가 공백으로 구분 지어 주어진다.

세 번째 줄에는 개의 영어 대문자 알파벳이 공백으로 구분 지어 주어지며 번째 알파벳은 번 마을에서 판매하는 열쇠고리에 적힌 알파벳이다.

네 번째 줄에는 선아의 친구의 이름이 주어진다. 친구의 이름은 길이 5의 서로 다른 영어 대문자 알파벳으로만 이루어진 문자열이다.

다섯 번째 줄부터 개의 줄에 걸쳐 각각 세 개의 정수 , , 가 공백으로 구분 지어 주어진다. 이는 마을 에서 로 가는 길이 의 단방향 도로가 존재한다는 의미이다.

출력

한 줄에 필요한 열쇠고리를 모두 모아서 마을 에서 마을 로 갈수 있는 최단 경로의 길이를 출력한다. 조건을 만족하는 경로가 존재하지 않을 경우 을 출력한다.