자동차 전시장

Sam은 자동차 전시장을 지을 도시를 결정하려고 합니다. 편의상 도시는 그래프 상에서의 노드에 대응되고, 각 도시들간의 이동가능 여부는 방향성 그래프로 나타내어집니다. 간선 하나를 지나는 데 걸리는 시간은 1초이며, 그래프는 n개의 노드와 m개의 간선으로 이루어져 있습니다.

자동차 전시장을 짓게 될 도시가 결정되면, 이 전시장에 관심이 있는 k명의 사람이 서로 다른 도시에서 출발하여 최단경로로 이동하여 전시장에 도달하게 됩니다. 이때 전시장에 도달하기까지 가장 오래 걸리는 사람의 시간이 최소가 되도록 전시장의 위치를 결정하는 프로그램을 작성해보세요.