릴레이 마라톤

당신은 베라푸르라는 나라의 마라톤 주최자 닐란(Nilan)입니다. 이 나라에는 N개의 도시가 있고, M개의 도로가 도시들을 잇고 있습니다. 도시는 1번부터 N번까지, 도로는 1번부터 M번까지 번호가 매겨져 있습니다. i번째 도로는 도시 u_i와 도시 v_i를 직접 연결하며, 이 도로를 지나는 데 w_i초가 걸립니다. 도로는 양방향이며, 자기 자신으로 가는 도로나 같은 두 도시를 잇는 중복 도로는 없습니다. N개의 도시 중 서로 다른 K개의 도시 A_1, A_2, ..., A_K는 특별 도시입니다.

릴레이 마라톤은 다음과 같이 진행됩니다. 두 무리의 사람들이 각각 출발 도시 start1과 start2에서 출발합니다. 먼저 start1의 무리가 finish1까지 이동합니다. 첫 번째 무리가 finish1에 도착하면, 지체 없이 두 번째 무리가 start2에서 finish2까지 이동을 시작합니다. 두 번째 무리가 finish2에 도착하면 릴레이가 끝납니다. 릴레이가 유효하려면 start1, finish1, start2, finish2가 모두 특별 도시이고 서로 달라야 합니다.

D(a, b)를 도시 a에서 도시 b까지 가는 최단 시간이라고 합니다. 경로가 없으면 D(a, b) = $\infty$로 둡니다. 유효한 릴레이의 총 시간은 D(start1, finish1) + D(start2, finish2)입니다. 모든 유효한 조합 (start1, finish1, start2, finish2) 중에서 이 총 시간의 최솟값을 구하세요.

입력에는 서로 다른 특별 도시 네 개 (a, b, c, d)가 항상 존재하며, D(a, b) + D(c, d) < $\infty$를 만족한다고 보장됩니다.

첫 줄에 정수 N, M, K가 주어집니다. 이어지는 M개의 줄에는 정수 u_i, v_i, w_i가 한 줄에 하나씩 주어지며, 이는 도시 u_i와 v_i 사이에 도로가 있고 어느 방향으로든 w_i초가 걸린다는 뜻입니다. 마지막 줄에는 서로 다른 특별 도시 A_1, A_2, ..., A_K가 주어집니다.

최솟값 D(start1, finish1) + D(start2, finish2)를 초 단위로 한 줄에 출력합니다.

$4 \le K \le N \le 10^5$

$2 \le M \le \min(N(N-1)/2, 3 \times 10^6)$

모든 $1 \le i \le M$에 대해 $1 \le w_i \le 1000$

모든 $1 \le i \le M$에 대해 $1 \le u_i \ne v_i \le N$