가장 먼저 만나는 두 사람

ACM 통신사가 새로 내놓은 "만남 경로" 앱을 홍보하려고 행사를 연다. 이 앱을 써서 가장 먼저 만난 두 사람에게 경품을 준다.

행사가 시작하기 직전, 모든 사람은 앱으로 서로의 위치를 알고 있다. 어떤 두 사람이 만나기로 정하면 두 사람은 앱이 알려준 최단 경로를 따라 서로를 향해 동시에 출발한다. 모든 사람의 이동 속도는 시속 10 km다. 두 사람 사이 최단 경로의 길이가 $d$ km라면 두 사람은 각각 $d/2$ km를 이동한 뒤에 만난다.

시상식을 준비하려면 행사가 끝나는 데 걸리는 최소 시간을 알아야 한다. 행사가 시작할 때 사람들의 위치와 그 지역의 지도가 주어질 때 이 시간을 구하자.

첫째 줄에 행사에 참여하는 사람 수 $N$, 지도에 있는 정점 개수 $K$, 정점을 잇는 길의 개수 $L$이 주어진다. ($2 \le N \le 100000$, $1 \le K \le 100000$, $1 \le L \le 100000$)

다음 $N$개의 줄에는 각 사람의 위치를 나타내는 수 $S_i$가 주어진다. ($1 \le S_i \le K$) $i$번째 사람이 $S_i$번 정점에 있다는 뜻이다. 여러 사람이 같은 정점에 있을 수도 있다.

다음 $L$개의 줄에는 길 하나의 정보가 $B_i$, $C_i$, $D_i$로 주어진다. ($1 \le B_i \ne C_i \le K$, $1 \le D_i \le 5000$) $B_i$번 정점과 $C_i$번 정점을 잇는 길이 $D_i$ km인 길이 있다는 뜻이다. 길은 양쪽 방향으로 다닐 수 있고, 같은 두 정점을 잇는 길이 여러 개 주어질 수도 있다.

어떤 두 사람이 만나는 데 걸리는 최단 시간을 분 단위로 구해 정수 하나를 출력한다. 서로 만날 수 있는 사람 쌍이 적어도 한 쌍 있다는 것은 보장된다. 두 사람이 같은 정점에서 출발하면 곧바로 만나므로 답이 0일 수도 있다.