리토 씨의 우체국

당신은 외딴섬 우체국에서 일하는 프로그래머이다. 당신이 사는 지역은 여러 섬으로 이루어져 있다. 각 섬에는 하나 이상의 항구 도시가 있다. 그 밖에 다른 도시나 마을이 있을 수도 있다. 어떤 섬에서 다른 섬으로 가려면 배를 이용해야 한다. 한 섬 안을 돌아다니는 데는 육로를 쓸 수 있지만, 해로를 이용하는 편이 더 빠를 때도 있다.

최근 우체국 민영화를 계기로 비용 절감을 위해 전국적으로 우편 배달원 감축이 이루어졌다. 외딴섬 우체국도 예외가 아니어서, 결국 우편 배달원은 리토 씨 한 명만 남게 되었다. 그 우체국이 집배를 담당하는 지역은 매우 넓어서 혼자 집배하기는 큰일이다. 그래서 어떻게 하면 효율적으로 집배할 수 있을지 리토 씨가 당신에게 도움을 청했다.

당신의 일은 리토 씨가 따라야 할 도시와 마을의 집배 순서가 주어졌을 때 최단 순회 경로를 구하는 프로그램을 작성하는 것이다.

리토 씨는 지정된 순서 외의 방식으로 집배 업무를 할 수 없다. 그러나 어떤 도시나 마을에서 다른 도시나 마을로 이동할 때 다른 도시나 마을을 경유하는 것은 허용된다. 또한 리토 씨는 섬들을 돌아다니기 위한 배 한 척을 가지고 있다.

예를 들어 도시 A, 도시 B, 마을 C라는 집배 순서가 주어졌다면, 도시 A에서 도시 B로 갈 때 어떤 도시나 마을을 경유해도 괜찮다. 이때 마을 C를 경유해도 괜찮지만, 집배 순서를 지키려면 일단 도시 B에 가서 집배를 한 뒤에 다시 마을 C를 방문해 집배해야 한다. 또 도시 A에서 해로를 이용해 도시 B로 가고 도시 B에서 육로를 이용해 마을 C로 갔다면, 배는 도시 B에 둔 채로 있게 된다. 따라서 다음에 해로를 이용하려면 도시 B로 돌아가야 한다.

한 도시나 마을에서 여러 번 집배해야 하는 경우도 있다. 예를 들어 도시 A, 마을 B, 도시 C, 마을 B라는 집배 순서가 주어질 수 있다. 이때 도시 A에서 마을 B를 거치지 않고 도시 C로 갔다면, 도시 C에서 곧바로 집배할 수는 없다. 첫 번째 마을 B에서의 집배가 끝나지 않았기 때문이다. 도시 C에서 집배를 마친 뒤에 마을 B를 방문해 집배해도 첫 번째 마을 B의 집배를 끝낸 것이 되지 않는다.

리토 씨는 처음에 반드시 어떤 항구 도시에 배와 함께 있다. 리토 씨는 베테랑이므로 이동 시간 외의 집배 작업에 걸리는 시간은 무시해도 된다. 또한 마지막 도시나 마을에서의 집배 업무가 완료될 때까지의 시간만 문제가 되며, 배를 원래 위치로 되돌려 우체국으로 돌아가는 시간은 고려하지 않아도 된다.

입력은 여러 데이터 세트로 구성된다. 각 데이터 세트의 형식은 다음과 같다.

N M
x1 y1 t1 sl1
x2 y2 t2 sl2
...
xM yM tM slM
R
z1 z2 ... zR

데이터 세트 안의 입력 항목은 모두 음이 아닌 정수이다. 행 안의 입력 항목 구분은 공백 1개이다.

첫 번째 행은 육로 및 해로망의 크기를 정한다.

N (2 ≤ N ≤ 200)은 도시 또는 마을의 수이다. 각 도시 또는 마을에는 1부터 N까지의 고유한 번호가 부여된다. M (1 ≤ M ≤ 10000)은 육로와 해로의 총 개수이다.

2행부터 1 + M행까지는 육로 또는 해로의 설명이다. xi와 yi (1 ≤ xi, yi ≤ N)는 양 끝 도시 또는 마을의 번호를 나타낸다. ti (1 ≤ ti ≤ 1000)는 그 육로 또는 해로의 이동 시간을 나타낸다. sli는 'L' 또는 'S' 중 하나이며, L은 육로를, S는 해로를 나타낸다.

어떤 두 도시나 마을을 직접 잇는 육로 또는 해로가 2개 이상 존재할 수 있다. 각 육로와 해로는 양방향이며, 즉 어느 방향으로든 이동할 수 있다.

M + 2행의 R (1 ≤ R ≤ 1000)은 리토 씨가 담당하는 집배 대상의 수를 나타낸다. M + 3행에는 집배 대상 도시나 마을의 번호 zi (1 ≤ zi ≤ N)가 집배 순서대로 R개 나열된다.

초기 상태에서 리토 씨와 배는 모두 항구 도시 z1에 있다. 초기 상태에서 집배 대상 도시나 마을로는 반드시 어떤 방법으로든 이동할 수 있다.

입력의 끝은 공백으로 구분된 두 개의 0을 포함하는 한 행으로 나타낸다.

입력의 각 데이터 세트에 대해 주어진 집배 순서대로 리토 씨가 도시와 마을을 순회하는 데 필요한 최단 이동 시간을 구해 한 행에 출력한다.