In and Out

젊은 해적 윌 트위스터는 아버지에게서 받은 소중한 메달을 잃어버렸습니다. 그 메달은 지금 구스 총독의 손에 있습니다. 메달이 너무나 소중한 윌은 그것을 되찾기로 마음먹습니다. 그는 닌자가 아니어서 존재를 완전히 숨길 수는 없으므로, 무사히 빠져나갈 확률을 높이기 위해 밤의 어둠을 틈타 움직이기로 합니다. 하지만 밤중에 마을을 돌아다니는 것은 의심을 사기 쉬워, 총독의 저택까지 가는 여정 역시 위험합니다.

마을 곳곳의 전략적으로 선택된 교차로에는 초병(한자리에 고정되어 지키는 보초)이 배치되어 있습니다. 윌은 싸움에 능하지 않아, 기습과 속도로 초병을 스쳐 지나가는 데 의존합니다. 그런데 만약 같은 초병을 가는 길과 오는 길에서 두 번 지나친다면, 두 번째에는 기습의 이점이 사라져 붙잡힐 위험이 큽니다. 그래서 그는 같은 초병을 두 번 지나가고 싶어 하지 않습니다.

윌의 여정은 항구에서 시작해 항구에서 끝나며, 그는 배를 타고 항구로 왔다가 다시 배로 떠납니다. 그는 초병의 위치가 표시된 마을 지도를 가지고 있습니다. 뛰어야 할 거리가 많으므로, 그는 어떤 초병도 두 번 넘게 지나가지 않으면서 총독의 저택까지 갔다가 돌아오는 가장 짧은 왕복 경로를 찾고자 합니다. 그가 이 경로를 찾도록 도와줄 수 있나요?

첫 줄에는 테스트 케이스의 수를 나타내는 정수 하나가 주어집니다. 각 테스트 케이스의 형식은 다음과 같습니다.

• 첫 줄에 두 정수 $N$과 $R$ ($2 \le N \le 1000$, $1 \le R \le 10000$)가 주어집니다. 각각 교차로의 수와 도로의 수입니다.
• 다음 $R$개의 줄에는 각각 세 정수 $a$, $b$, $l$ ($1 \le a, b \le N$, $1 \le l \le 1000$)이 주어지며, 교차로 $a$와 $b$ 사이에 길이가 $l$인 양방향 도로가 있음을 뜻합니다.
• 그다음 줄에 정수 $S$ ($0 \le S \le \min(N - 2, 100)$)가 주어집니다. 초병의 수입니다.
• 그다음 줄에 서로 다른 $S$개의 정수 $s_i$ ($2 \le s_i < N$)가 주어지며, 초병이 있는 교차로들을 나타냅니다.

교차로는 $1$번부터 $N$번까지 번호가 매겨져 있습니다. 윌의 배는 $1$번 교차로에 있고, 총독의 저택은 $N$번 교차로에 있습니다. 배에서 총독의 저택까지 가는 경로는 반드시 존재함이 보장됩니다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력합니다. 윌이 왕복(총독의 저택까지 갔다가 다시 돌아오는 전체 경로) 동안 이동해야 하는 최소 총 거리입니다. 만약 각 초병을 최대 한 번씩만 지나가는 왕복 경로가 존재하지 않는다면, 대신 한 줄에 No safe route(따옴표 제외)를 출력합니다.