소방차

문제 정보

문제

한겨울 날씨가 추워지면 각종 난방 기구 때문에 화재가 발생하기 쉽습니다. 어느 추운 겨울날 서울 시내 n개의 지역에 동시에 화재가 발생했습니다. 피해를 최소화하기 위해 가능한 한 빠르게 소방차를 파견해야 합니다. 서울 시내에는 m개의 소방서가 있습니다. 화재 장소에서 가장 가까운 소방서에서 소방차를 보낸다고 할 때, 각 화재 장소에 소방차가 도달하기까지 걸리는 시간의 합을 계산하는 프로그램을 작성하세요. 각 소방서에는 소방차가 충분히 많습니다.

이 문제에서 서울 시내는 1부터 V까지 번호 붙여진 V개의 장소들과 이들을 연결하는 E개의 양방향 도로로 구성됩니다. 모든 도로에 대해 도로가 연결하는 두 장소의 번호와 각 도로별 통행 소요 시간이 주어집니다.

예제 지도를 봅시다. 사각형으로 표시된 지점들은 소방서를, 음영으로 칠해진 지점들은 불이 난 지점을 나타냅니다. 2번과 5번 장소에서는 6번 소방서가 가장 가깝고, 3번 장소에서는 4번 소방서가 가장 가깝습니다. 이때, 각 장소에 소방차가 도착하기까지 걸리는 시간은 2번 장소에 8분, 5번 장소에 4분, 3번 장소에 4분으로 총 합은 16분이 됩니다.

입력

입력의 첫 번째 줄에는 테스트 케이스의 수 C(1≤C≤50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 장소의 수 V(2≤V≤1000)와 도로의 수 E(0≤E≤V*(V-1)/2) 그리고 화재 장소의 수 n과 소방서의 수 m(1≤n, 1≤m, n+m≤V)이 주어집니다. 그 후 e 줄에 각 세 개의 정수로 각 도로가 잇는 두 장소 a, b의 번호와(1≤a, b≤V) 이 도로를 통행하는 데 걸리는 시간 t가 분 단위로 주어집니다.(1≤t≤100) 테스트 케이스의 마지막 두 줄에는 각각 n개와 m개의 정수로, 화재가 발생한 장소의 번호와 소방서의 위치 번호가 주어집니다.

소방서가 있는 곳에서는 화재가 발생하지 않으며, 소방차가 도착할 수 없는 화재 장소는 없다고 가정해도 좋습니다. 입력에서 같은 장소 사이에 두 개 이상의 도로가 존재하는 일은 없으며, 모든 도로는 양방향 통행이 가능합니다.

출력

각 테스트 케이스마다 한 줄로, 각 화재 장소에 소방차가 도착하기까지 걸리는 시간의 합을 분 단위로 출력합니다.

예제 입력

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

예제 출력

16

노트

7개의 댓글이 있습니다.