재배치

요리사 학교를 마친 치훈이는 식당 개업을 준비하고 있습니다. 그는 통근 거리를 최소화하기 위해 새로운 식당을 개업할 최적의 장소를 찾고자 합니다. 이를 위해 최적 동선 개발 업무를 의뢰합니다.

치훈이가 이사를 계획하는 지역에는 N 개(1 <= N <= 10,000)의 마을과 마을을 연결하는 M 개(1 <= M <= 50,000)의 양방향 도로가 있습니다. 모든 마을은 도로로 연결되어 있습니다. 치훈이는 식당과 집을 오고가는 통근 거리를 최소화할 수 있는 마을을 선택하는 데 도움이 필요합니다.

치훈이가 매일 방문하려는 K 개(1 <= K <= 5)의 마을엔 시장이 있습니다. 특히, 매일 그는 식당을 떠나 시장이 있는 K 마을을 방문하고 식당으로 돌아갑니다. 치훈이는 원하는 순서대로 시장을 방문할 수 있습니다. 다만, 치훈이가 식당을 개업할 마을을 선택할 때, N-K 마을 중에서 시장이 없는 마을만 선택합니다.

개발자인 당신은, 치훈이의 식당 개업 최적 장소와 시장을 방문하는 최적 동선을 개발하여 최소 거리로 이동할 수 있도록 문제를 해결해야 합니다.

• 1번째 줄: 세 개의 공백으로 구분된 정수, N, M, K.
• 2번째 줄..1+K: i+1번째 줄에는 i번째 시장이 있는 마을을 나타내는 1...N 사이의 정수가 포함됩니다. 각 시장은 다른 마을에 있습니다.
• 2번째 줄+K..1+K+M: 각 줄은 3 개의 공백으로 구분 된 정수, i, j (1 <= i,j <= N), 및 L (1 <= L <= 1000)을 포함하여 마을 i에서 마을 j까지의 길이 L의 도로가 있음을 나타냅니다.

• 1번째 줄: 치훈이가 식당을 최적의 위치에서 개업하고 매일 통근할 때 이동해야 할 최소 거리입니다.