23975번 - 정훈이는 민트초코맛 짜장라면이 먹고 싶다

정훈이는 민트초코맛 짜장라면을 좋아한다.

그러나 민트초코맛 짜장라면을 찾는 사람은 정훈이밖에 없기 때문에 친절한 정훈이는 편의점 사장님들을 위해 자신이 언제, 어떤 편의점을 방문할지 미리 알려주려고 한다.

앞으로 K일 동안, 정훈이는 집에 가는 길에 있는 편의점 중에서 재고가 있는 첫 편의점에 방문해 민트초코맛 짜장라면을 1개씩 구매할 예정이다. 민트초코맛을 좋아하는 정훈이도 하루에 2개 이상 먹는 것은 힘들기 때문에 하루에 구매하는 라면은 한 개를 넘지 않는다.

편의점은 1번부터 N번까지 규모 순으로 번호가 매겨져 있으며, 정훈이네 집은 규모가 가장 작은 1번 편의점이 위치한 곳에 있다. 정훈이는 편의점을 잇는 M개의 양방향 길로만 다니면서 항상 최단 경로로 집에 간다. 단, 최단 경로가 여러 개라면 바로 다음에 보이는 편의점의 규모가 더 큰 쪽을 선택한다.

K일 동안 정훈이가 위치한 곳의 편의점 번호가 주어질 때, 어떤 편의점에서 민트초코맛 짜장라면을 구매할지 구하여라.

첫 줄에 N, M, K가 공백으로 구분되어 주어진다. (1 ≤ N, M, K ≤ 1,000,000)

둘째 줄에 각 편의점에 남아있는 민트초코맛 짜장라면의 개수 A_i가 주어진다. (0 ≤ A_i ≤ 100)

셋째 줄부터 M+2번째 줄까지 두 편의점의 번호와 두 편의점을 잇는 길의 거리인 정수 C가 주어진다. (1 ≤ C ≤ 1,000) 

M+3번째 줄부터 M+2+K번째 줄까지 정훈이가 있는 곳의 편의점 번호가 주어진다.

K일 동안 정훈이가 민트초코맛 짜장라면을 구매할 편의점 번호를 출력한다.

집으로 가는 길이 없거나 라면을 구매할 수 없다면 -1을 출력한다.