문제
최근 여러분이 살고 있는 시는 최근 크고 자연 그대로인 땅을 구매했고, 이 땅을 등산로가 있는 자연 공원으로 개발하고 싶어 한다. 이 땅은 관광객이 등산을 하고 싶어 하는 n개의 흥미로운 장소가 있으며, 그 중 k개는 매우 특별하다.
시는 이 장소들을 양방향 통행이 가능한 등산로로 연결하고 싶어 한다. 시는 m개의 다양한 비용을 가진, 서로 다른 두 장소를 연결하는 등산로 후보를 정했다. 등산로를 선택하는 데에는 다음과 같은 제한이 있다.
- 장소에서 다른 장소로 이동하는 길은 단 하나여야 한다.
- w개의 등산로만 특별한 장소끼리를 연결하여야 한다.
물론, 시는 등산로를 개발하는 비용의 합을 최소로 하기를 원한다.
입력
첫 번째 줄에는 n, m, k, w가 주어진다. (2 ≤ n ≤ 2x105, 1 ≤ m ≤ 5x105, 1 ≤ k < n, 1 ≤ w < n)
다음 k개의 줄에는 특별한 장소의 번호를 나타내는 숫자 s가 주어진다. (1 ≤ s ≤ n) 이 값은 겹치지 않으며, 증가하는 순서로 주어진다.
다음 m개의 줄에는 등산로의 후보가 주어진다. i번째 줄은 3개의 정수 ai, bi, ci가 주어지며, 이 것은 장소 ai와 장소 bi를 연결하는 비용 ci인 등산로가 있다는 뜻이다. 두 도시를 연결하는 등산로는 최대 하나이다. (1 ≤ a, b ≤ n, a ≠ b, 1 ≤ c ≤ 105)
출력
첫 번째 줄에, 만약 제한을 만족하도록 등산로를 선택할 수 없다면 -1을, 있다면 비용의 최솟값을 출력하여라.
예제 #1
3 3 1 2
2
1 2 2
1 3 1
2 3 3
5
예제 #2
3 1 1 1
2
1 2 2
-1
출처
North American Invitational Programming Contest 2017 E번
로그인해야 코드를 작성할 수 있어요.