27455번 - 카드캡터 한별

어느 날, 평범한 일상을 보내던 한별이는 마법소녀가 되었습니다. 마법소녀가 된 한별이는 더욱더 강해져서 악의 세력 “보기 (bogy)”의 간부들을 토벌하기로 결심했습니다. 하지만 한별이는 마법에 능숙하지 못하기 때문에 먼저 마력만 있다면 마법을 사용할 수 있게 해주는 “스타더스트 카드” $N$장을 전부 수집하기로 했습니다.

한별이가 사는 지역은 정점이 $V$개, 간선이 $E$개인 방향 그래프로 나타낼 수 있습니다. 각 정점에는 $1$번부터 $V$번까지 번호가 붙어 있고, 간선마다 길이가 정해져 있습니다. 한별이는 처음에 $1$번 정점에서 시작하고, “스타더스트 카드”는 $N$개의 목표 정점에 하나씩 배치되어 있습니다. 한별이가 각 목표 정점을 처음으로 방문하면 “스타더스트 카드”를 하나 얻습니다. 한별이가 “스타더스트 카드”를 수집한다는 정보를 얻은 “보기”는 모든 정점에 “보기”의 간부들을 한 명씩 배치했습니다. 한별이는 “보기”의 방해를 받지 않기 위해서 한별이가 가진 카드 개수보다 간부의 힘이 작거나 같은 정점으로만 다녀야 합니다. 한별이가 카드 $L$장을 가진채로 어떤 정점으로 이동하려 할 때, 그 정점에서의 카드 유무와 상관없이 간부의 힘이 $L$ 이하여야 이동할 수 있습니다.

한별이가 “스타더스트 카드”를 빠르게 수집할 수 있도록 한별이의 이동 방법의 최소 이동 거리를 출력해주세요! 단, 한별이는 “스타더스트 카드” $N$장을 모두 수집하면 즉시 이동을 종료합니다.

첫 번째 줄에 $N$, $V$, $E$가 주어집니다. ($1\leq N\leq\min(14,V-1)$, $1\leq V\leq 1\, 000$, $1\leq E\leq \min(5\, 000,V(V-1)))$

두 번째 줄에 $V$ 개의 정수 $l_1, l_2, \cdots ,l_V$가 주어집니다. $l_i$는 $i$ 번 정점에 위치한 “보기” 간부의 힘을 의미합니다. ($l_1=0$, $2\leq i\leq V$에 대해 $0\leq l_i\leq N-1$)

세 번째 줄에 목표 정점의 정점 번호를 의미하는 $N$ 개의 서로 다른 정수 $k_1, k_2, \cdots ,k_N$가 오름차순으로 주어집니다. ($2\leq k_i\leq V$)

네 번째 줄부터 $E$개의 줄에 각 간선의 시작점과 끝점의 번호 $s,e$와 간선의 길이 $d$가 주어집니다. ($1\leq s, e \leq V$, $s \neq e$, $1\leq d\leq 10^{9}$)

단, 양 끝점이 모두 같은 간선이 둘 이상 입력되지 않습니다.

한별이가 모든 카드를 모을 수 있는 경로들 중 최소 이동 거리를 출력합니다. 만약 한별이가 모든 카드를 모을 수 없는 경우, $-1$을 출력합니다.