상근이가 지배하는 나라에는 도시가 N개 있고, 도시는 M개의 양방향 도로로 연결되어 있다.

이 중 K개 도시에는 쇼핑몰이 있고, 국민은 도로를 통해서 쇼핑몰이 있는 마을로 가고, 쇼핑을 한다.

쇼핑몰이 멀리 떨어져 있는 사람은 쇼핑몰로 가기 위해 긴 시간 운전을 해야 한다.

상근이는 실정을 파악하기 위해서 쇼핑몰과 집의 최단 거리가 집의 위치에 따라서 어떻게 달라지는지 구하기로 한다.

집은 도시에 있을 수도 있고, 도로 위에 있을 수도 있다.

도로의 정보와 쇼핑몰이 있는 도시가 주어졌을 때,

쇼핑몰이 있는 도시와 가장 먼 거리에 있는 집까지의 거리를 구하는 프로그램을 작성하시오.

도시 속을 이동하는데 걸리는 시간은 0이다.

또, 사람들은 항상 최단 경로를 이용한다.

쇼핑몰 timer 1s memory 256MB

쇼핑몰 1s 256MB