탐사 계획

Bubble Cup X의 참가자들은 대회가 끝난 뒤 모여 개최국과 그 도시들을 알아보는 가장 좋은 방법이 무엇인지 논의했다.

한동안 Serbia의 지도를 살펴본 참가자들은 다음과 같은 사실을 알아냈다. 이 나라에는 1부터 V까지의 번호가 매겨진 V개의 도시가 있으며, 도시들을 연결하는 E개의 bi-방향 도로가 있다. 각 도로에는 가중치(그 도로를 건너는 데 필요한 시간)가 있다. Bubble Cup에는 N개의 팀이 있으며, 참가자들은 다음과 같은 계획을 세웠다. N개 팀은 각각 V개 도시 중 한 곳에서 여정을 시작하며, 일부 팀은 시작 위치가 같다.

그들은 모든 팀이 T분 동안 이동할 수 있고 최종적으로 도착한 서로 다른 도시의 수가 적어도 K개가 되는 가장 짧은 시간 T를 찾고자 한다(팀들이 최종적으로 도착한 도시들만 알게 되기 때문이다). 팀이 항상 이동하고 있어야 하는 것은 아니다. 특정 도시가 마음에 들면 그곳에 머물면서 시간이 지나기를 기다릴 수 있다.

참가자들이 적어도 K개의 서로 다른 도시에 도착할 수 있게 하는 가장 짧은 시간 T를 구하도록 도와주거나, 어떻게 이동하더라도 불가능하다면 -1을 출력한다.

일부 도시 사이에는 여러 개의 도로가 존재할 수 있음에 유의한다.

첫째 줄에는 네 정수 V, E, N and K (1 ≤ V ≤ 600, 1 ≤ E ≤ 20000, 1 ≤ N ≤ min(V, 200), 1 ≤ K ≤ N)이 주어지며, 각각 도시의 수, 도로의 수, 팀의 수, 그리고 팀들이 최종적으로 도착해야 하는 서로 다른 도시 수의 최솟값을 뜻한다.

둘째 줄에는 팀들이 여정을 시작하는 도시를 나타내는 N개의 정수가 주어진다.

다음 Next E개의 줄에는 도로에 관한 정보가 Ai Bi Ti (1 ≤ Ai, Bi ≤ V, 1 ≤ Ti ≤ 10000) 형식으로 주어진다. 이는 도시 Ai and Bi를 연결하는 도로가 있으며, 그 도로를 건너는 데 Ti분이 필요하다는 뜻이다.

팀들이 적어도 K개의 서로 다른 도시에 도착할 수 있도록 이동할 수 있는 최소 시간을 나타내는 정수 하나를 출력하거나, 해가 없다면 -1을 출력한다.

해가 존재한다면 결과는 1731311보다 크지 않다.

세 팀은 도시 5에서 시작하고, 두 팀은 도시 2에서 시작한다. 이들이 3분 동안 이동하기로 합의하면 가능한 상황 중 하나는 다음과 같다. 도시 2에 두 팀, 도시 5에 한 팀, 도시 3에 한 팀, 도시 1에 한 팀이 있게 된다. 따라서 팀들이 여정을 마치는 서로 다른 도시가 네 곳임을 알 수 있다.