문제
1월 1일 연휴에 학원에 나오지 않은 학생들은 선생님들 몰래 같은 PC방에서 모여 LOL을 하고자 한다.
그러나 모든 학생들이 게으르기로 유명한 학생들이고 서로 떨어져 살고 있는 학생들도 있기 때문에 어디서 모여서 게임을 할지를 고민하고 있다.
그러던 도중에 가장 노는데 잔머리를 잘 굴리는 동욱이가 모든 학생의 이동시간의 합이 최소가 되는 지점에서 만나고자 제안을 했고,
다른 학생들도 흔쾌히 동의를 하였다. 하지만 맨날 노는 데만 집중해서 공부를 소홀히 했던 학생들은 이 문제를 제대로 해결하지 못하고
그나마 열심히 하는 축에 속하는 당신에게 프로그램을 짜달라고 요청하였다.
학생들이 사는 장소와 두 개의 장소를 잇는 경로의 이동시간이 주어지고 어떤 장소에서 모두 같이 모였을 경우,
모든 학생의 이동 시간의 합의 최소를 구하는 프로그램을 작성하라.
입력
입력의 첫 번째 줄에는 학생의 수 N(1≤N≤500), 장소의 수P(1≤P≤800), 그리고 장소를 잇는 경로의 수C(1≤C≤1,450)이 입력된다.
그 다음 줄부터 C개의 줄에는 3개의 정수 i, j, cost가 입력되는데 i번 장소와 j번 장소를 잇는 경로로 이동할 경우 cost만큼의 이동시간이 걸린다는 것이다.
i번 장소에서 j번 장소로 이동하거나 j번 장소에서 i번 장소로 이동하는 것이 다 가능하다(1≤i, j≤P, 1≤cost≤225)
마지막으로 한 줄에는 N명의 학생이 현재 위치한 장소의 번호가 입력된다.
한 장소에 여러 명의 학생이 있을 수 있음에 유의하라.
출력
모든 학생들이 한 장소에 모였을 때 이동시간의 합의 최소를 출력한다.
예제1
입력
345
121
135
237
243
345
234
출력
8