시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 256 MB 45 21 15 42.857%

문제

사과나라에는 n 개의 도시들이 존재하며, 이 중 k 개의 도시는 국왕 구사과가 자주 방문하는 중요한 도시들이다. 또한 사과나라에는 m 개의 도시와 도시를 잇는 도로가 존재한다. 각각의 도시들은 1~n의 번호가 매겨져 있다.

어느 날 갑자기 사과나라에 폭풍이 몰아쳤다. 이 폭풍은 사과나라 건국 이래 최대 규모의 자연 재해였으며, 이 때문에 모든 도로들은 제 구실을 하지 못하게 되었다. 따라서 사과나라의 대신들은 도시들 간의 교류를 이어나가기 위해 도로들을 재건하기로 결정하였다. 이를 위해, 대신들은 각각의 도로를 재건하는 데 드는 비용을 조사하여 알아내었다.

그러나, 평소 사치와 향락에 찌든 생활을 하던 구사과 때문에 사과나라의 국고는 텅텅 비어버렸고, 이 때문에 모든 도로를 재건할 수는 없었다. 대신들은 일단 급한 대로 모든 중요한 도시가 서로 이어질 수 있도록 (즉, 각각의 중요한 도시들에서 다른 모든 중요한 도시에 도달할 수 있도록) 우선적으로 도로를 재건하고자 한다.

대신들은 세계 최고의 프로그래머인 당신에게 모든 중요한 도시가 서로 이어질 수 있도록 도로를 재건하는 최소 비용을 알아내도록 의뢰하였다. 우매한 사과나라 사람들에게 당신의 실력을 보여 주자.

입력

첫 번째 줄에는 도시의 개수 n, 중요한 도시의 개수 k, 도로의 개수 m이 공백으로 구분되어 주어진다.

두 번째 줄에는 공백으로 구분된 k개의 수들이 주어진다. 이 수들은 1 이상 n 이하의 서로 다른 정수들로, 중요한 도시들의 번호를 나타낸다.

다음 줄부터는 m개의 줄에 걸쳐 각 도로에 대한 정보가 주어진다. 각 줄에는 세 정수 a, b, c가 주어진다. 이는 이 도로가 도시 a와 도시 b를 잇고 있으며, 이 도로를 재건하는 데에 c의 비용이 소모된다는 뜻이다.

모든 도시들이 도로를 통해 연결되어 있음을 가정해도 좋다.

  • 1 ≤ c ≤ 109
  • n ≥ k
  • 2 ≤ k ≤ 5
  • n ≤ 105
  • 1 ≤ m ≤ 2 ⋅ 105

출력

당신은 모든 중요한 도시가 서로 이어질 수 있도록 도로를 재건하는 최소 비용을 하나의 정수로 출력해야 한다.

예제 입력

4 3 6
1 3 4
1 2 4
1 3 9
1 4 6
2 3 2
2 4 5
3 4 8

예제 출력

11

힌트

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2016 4번

  • 문제를 번역한 사람: khsoo01