농장 이전

농부 John이 이사를 준비하고 있습니다! 그는 매일 이동해야 하는 거리를 최소화할 수 있도록 새 농장을 지을 최적의 위치를 찾으려 합니다.

John이 이사할 지역에는 $N$개의 마을이 있습니다 ($1 \le N \le 10000$). 특정 마을 쌍을 잇는 양방향 도로가 $M$개 있습니다 ($1 \le M \le 50000$). 모든 마을은 도로들을 적절히 조합하면 서로 오갈 수 있습니다. John은 새 농장을 지을 가장 좋은 마을을 고르는 데 도움이 필요합니다.

$K$개의 마을에는 시장이 있으며 ($1 \le K \le 5$), John은 매일 이 시장들을 모두 방문하려 합니다. 구체적으로 그는 매일 새 농장을 나서서 시장이 있는 $K$개의 마을을 모두 방문한 뒤 다시 농장으로 돌아옵니다. 시장을 방문하는 순서는 자유롭게 정할 수 있습니다. 농장을 지을 마을을 고를 때, 집값이 더 싼 곳을 원하므로 시장이 없는 $N-K$개의 마을 중에서만 고릅니다.

John이 농장을 최적의 위치에 짓고 시장을 방문하는 순서도 가장 현명하게 정했을 때, 하루에 이동해야 하는 최소 거리를 구하세요.

• 첫째 줄: 공백으로 구분된 세 정수 $N$, $M$, $K$.
• 다음 $K$개의 줄: $i$번째 줄에는 $i$번째 시장이 있는 마을의 번호가 주어집니다 ($1 \le$ 번호 $\le N$). 각 시장은 서로 다른 마을에 있습니다.
• 그다음 $M$개의 줄: 각 줄에는 공백으로 구분된 세 정수 $i$, $j$ ($1 \le i, j \le N$), $L$ ($1 \le L \le 1000$)이 주어지며, 마을 $i$와 마을 $j$를 잇는 길이 $L$의 도로가 있음을 뜻합니다.

• 첫째 줄: John이 농장을 최적의 위치에 지었을 때 하루에 이동해야 하는 최소 거리를 출력합니다.

예를 들어 마을이 $5$개, 도로가 $6$개이고 마을 $1$, $2$, $3$에 시장이 있다고 합시다. 이때 John은 마을 $5$에 농장을 짓는 것이 최적입니다. 하루 경로는 $5 \to 1 \to 2 \to 3 \to 2 \to 1 \to 5$가 되어 총 이동 거리는 $12$입니다.