문제 설명
JOI 왕국에는 $N$개의 마을이 있으며, 그 사이에는 양방향으로 통행 가능한 $M$개의 도로가 연결되어 있다. $K$개의 마을에는 쇼핑몰이 있어서, 국민들은 도로를 통해 그 마을들 중 한 곳으로 가서 쇼핑을 한다.
집의 위치에 따라서는 쇼핑을 하러 가기 위해 긴 거리를 이동해야 할 필요가 있으며, 이는 매우 불편하다. 국왕은 이러한 실정을 파악하기 위해, 쇼핑몰이 있는 마을까지의 최단 거리가 집의 위치에 따라 얼마나 길어질 수 있는지를 조사하기로 했다. 집은 도로 도중에 지어질 수도 있으므로(입력 예제 $1$의 설명 참조), 이 조사는 매우 힘들다. 그래서 국왕은 우수한 프로그래머인 당신에게 조사를 수행하는 프로그램 작성을 의뢰했다.
도로의 정보와 쇼핑몰이 있는 마을의 정보가 주어질 때, 쇼핑몰이 있는 마을로부터 가장 먼 도로 위의 점(끝점 포함)까지의 거리를 구하는 프로그램을 작성하시오. 마을 안을 이동하는 데 걸리는 거리는 무시해도 좋다.
입력
표준 입력에서 다음 입력을 읽어 들이시오.
- $1$번째 줄에는 정수 $N, M, K$가 공백으로 구분되어 적혀 있다. $N$은 JOI 왕국의 마을의 개수를, $M$은 JOI 왕국의 도로의 개수를, $K$는 쇼핑몰이 있는 마을의 개수를 각각 나타낸다. 마을에는 $1, 2, \dots, N$의 번호가 매겨져 있다.
- 이어지는 $M$개의 줄은 도로의 정보를 나타낸다. $(i + 1)$번째 줄($1 \le i \le M$)에는 정수 $a_i, b_i, l_i$($1 \le a_i \le N, 1 \le b_i \le N, 1 \le l_i \le 1000$)가 공백으로 구분되어 적혀 있다. 이는 $i$번째 도로가 마을 $a_i$와 마을 $b_i$를 연결하고 있으며, 길이가 $l_i$임을 나타낸다. 도로의 양 끝이 같은 마을인 경우는 없다. 또한, 임의의 $2$개의 마을 $p, q$에 대해 $p$와 $q$를 연결하는 도로는 $2$개 이상 존재하지 않는다. 어느 마을에서 어느 마을로든 몇 개의 도로를 따라 이동할 수 있다.
- 이어지는 $K$개의 줄은 쇼핑몰의 정보를 나타낸다. $(i + M + 1)$번째 줄($1 \le i \le K$)에는 $1$개의 정수 $s_i$($1 \le s_i \le N$)가 적혀 있다. 이는 마을 $s_i$에 쇼핑몰이 있음을 나타낸다. $s_1, \dots, s_K$ 중에 같은 값이 $2$번 이상 나타나는 경우는 없다.
출력
표준 출력에 쇼핑몰이 있는 마을까지의 최단 거리의 최댓값을 소수점 첫째 자리에서 반올림한 정수 $1$개를 출력하시오.
예제
예제 1
입력
3 3 1 1 2 1 2 3 1 3 1 1 1
출력
2
설명
입력 예제 $1$은 다음과 같은 마을을 나타낸다. 도로의 길이는 모두 $1$이다. 쇼핑몰은 마을 $1$에만 있다.
쇼핑몰이 있는 마을까지 가장 먼 점은 마을 $2$와 마을 $3$을 연결하는 도로 위의, 마을 $2$로부터 거리 $0.5$인 위치에 있는 점이며, 쇼핑몰이 있는 마을까지의 거리는 $1.5$이다. 따라서 이를 반올림한 값인 $2$를 출력한다.
예제 2
입력
4 5 2 1 2 4 1 3 1 2 3 2 2 4 2 3 4 1 2 4
출력
3
제약 조건
- $2 \le N \le 3000$: JOI 왕국의 마을의 개수.
- $1 \le M \le 100000 = 10^5$: JOI 왕국의 도로의 개수.
- $1 \le K \le N$: 쇼핑몰이 있는 마을의 개수.
- $1 \le l_i \le 1000$: $i$번째 도로의 길이.
채점 기준
- 채점용 데이터 중 배점의 $40\%$ 분량에 대해서는 $K = 1$을 만족한다.