달콤한 버터

농부 FJ는 위스콘신에서 가장 달콤한 버터를 만드는 비결을 찾아냈다. 바로 설탕이다. 목초지에 설탕 덩어리를 놓아두면 소 $N$마리($1 \le N \le 500$)가 그것을 핥고, 그 결과 초달콤 버터가 만들어져 더 비싼 값에 팔린다. FJ는 남은 돈으로 소들에게 사치품을 사 준다.

FJ는 교활하다. 옛날 파블로프처럼 소들이 종소리를 들으면 특정 목초지로 가도록 훈련시켰다. 그는 설탕을 그 목초지에 놓고, 오후 한가운데에 종을 울려 저녁 착유 때 완벽한 우유가 나오게 한다.

FJ는 각 소가 어느 목초지에서 시간을 보내는지 알고 있다. 여러 마리가 같은 목초지에 있을 수도 있다. 소들의 목초지 위치와 목초지를 잇는 길 정보가 주어진다. FJ가 종을 울렸을 때 소들이 걷는 총 거리가 최소가 되도록 설탕을 놓을 목초지를 찾아라. 목초지들은 충분히 연결되어 있어서 항상 해가 존재한다.

첫 줄에 소의 수 $N$, 목초지의 수 $P$($2 \le P \le 800$), 길의 수 $C$($1 \le C \le 1450$)가 공백으로 구분되어 주어진다. 소는 1번부터 $N$번까지, 목초지는 1번부터 $P$번까지 번호가 매겨져 있다.

둘째 줄부터 $N$개의 줄에 소가 풀을 뜯고 있는 목초지 번호가 한 줄에 하나씩 주어진다. $i$번째 소의 목초지는 $i+1$번째 줄에 있다.

이어서 $C$개의 줄에 길 정보가 주어진다. 각 줄에는 길이 잇는 두 목초지 번호와 길의 길이(1 이상 225 이하)가 주어진다. 길은 양방향으로 지날 수 있다. 같은 두 목초지를 직접 잇는 길은 하나뿐이다.

설탕이 놓인 목초지까지 소들이 걷는 거리의 합의 최솟값을 한 줄에 출력한다.

아래 그림은 목초지들의 연결 관계를 기하학적으로 보여준다.

          P2
 P1 @--1--@ C1
     \    |\
      \   | \
       5  7  3
        \ |   \
         \|    \ C3
       C2 @--5--@
          P3    P4

설탕을 4번 목초지에 놓으면 1번 소는 3만큼, 2번 소는 5만큼 걷고, 3번 소는 0만큼 걷는다. 합은 8이다.