시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB67272238.596%

문제

ACM 통신사에서는 새로 출시한 “만남 경로” 어플리케이션을 홍보하기 위해, 행사를 개최하고 있다. 이 서비스를 이용하여 가장 먼저 만난 두 사람에게 경품을 제공하는 행사이다.

행사가 시작하기 직전, 모든 사람은 어플리케이션을 통해 서로의 위치를 알고 있다. 만약 어떤 두 사람이 만나기로 결정했다면, 이 두 사람은 어플리케이션이 제공해준 최단 경로를 따라서 서로를 만나기 위해 이동하게 된다. 모든 사람의 이동 속도는 10km/h이다.

시상식을 준비하기 위해, ACM 통신사에서는 행사가 끝나는 데 걸리는 최소한의 시간을 알고 싶어한다. 행사가 시작할 때 사람들의 위치와 해당 지역의 지도가 주어질 때, 이 시간을 구하는 것을 도와주자.

입력

첫 번째 줄에는 행사에 참여하는 사람 수 N, 지도상의 정점 개수 K, 정점들을 잇는 길의 개수 L이 주어진다. (2 ≤ N ≤ 100,000; 1 ≤ K ≤ 100,000; 1 ≤ L ≤ 100,000)

다음 N개의 줄에는 각 사람들의 위치를 나타내는 숫자 Si가 주어진다. (1 ≤ Si ≤ K) 이는 i번째 사람이 Si번째 정점에 있음을 의미한다.

다음 L개의 줄에는 각각의 길에 대한 정보가 Bi, Ci, Di로 주어진다. (1 ≤ Bi ≠ Ci ≤ K, 1 ≤ Di ≤ 5000) 이는 Bi와 Ci를 잇는 길이 Di km짜리 길이 존재함을 의미한다.

출력

어떤 두 사람이 만나는 데 걸리는 최단 시간을 분 단위로 구하여 하나의 자연수로 출력한다. 서로 만날 수 있는 사람 쌍이 적어도 한 쌍은 존재한다는 것은 보장된다.

예제 입력 1

2 2 1
1
2
1 2 5

예제 출력 1

15

예제 입력 2

3 3 3
1
2
3
1 2 4
3 2 4
3 1 4

예제 출력 2

12

예제 입력 3

2 3 3
1
2
1 2 9
3 2 5
1 3 3

예제 출력 3

24

출처

  • 어색한 표현을 찾은 사람: jh05013