쇼핑

새 아파트로 막 이사를 와서 사야 할 물건이 잔뜩 있다. 그런데 이 많은 물건을 사려면 여러 상점을 돌아다녀야 한다. 필요한 물건을 모두 사는 데 드는 운전 거리를 최소로 하고 싶다.

도시는 여러 교차로가 도로로 연결된 형태로 이루어져 있다. 집과 모든 상점은 각각 어떤 교차로에 위치한다. 집에서 출발하여 방문해야 하는 모든 상점을 들른 뒤 다시 집으로 돌아오는 가장 짧은 경로의 길이를 구하여라.

첫째 줄에 테스트 케이스의 개수를 나타내는 정수 하나가 주어진다. 각 테스트 케이스의 첫째 줄에는 도시의 교차로 수 $N$ 과 도로 수 $M$ 이 주어진다 ($1 \le N \le 100000$, $1 \le M \le 100000$). 교차로는 $0$ 번부터 $N-1$ 번까지 번호가 매겨져 있으며, 집은 $0$ 번 교차로에 있다. 이어지는 $M$ 개의 줄에는 각각 세 정수 $X$, $Y$, $D$ 가 주어지며, 이는 교차로 $X$ 와 $Y$ 가 길이 $D$ 인 양방향 도로로 연결되어 있음을 뜻한다. 그다음 줄에는 방문해야 하는 상점의 수 $S$ 가 주어진다 ($1 \le S \le 10$). 이어지는 $S$ 개의 줄에는 각 상점이 위치한 교차로의 번호가 한 줄에 하나씩 주어진다. 모든 상점은 집에서 도달할 수 있다.

각 테스트 케이스마다, 집에서 출발하여 모든 상점을 방문하고 다시 집으로 돌아오는 가장 짧은 쇼핑 경로의 길이를 정수 하나로 한 줄에 출력한다.