침공이 일어난다면, 제발...

Curiosity가 화성에서 물을 발견했을 뿐만 아니라, 공격적이고 피에 굶주린 외계인 무리도 발견한 뒤, Louvain-la-Neuve 시 정부는 예방 조치를 취하기로 했다. 외계인의 공격이 일어날 경우 도시의 모든 사람을 대피시킬 수 있도록 대피소를 지은 것이다.

도시 곳곳에 외계인에 대비한 대피소 여러 개가 세워져 있으며, 시민들은 그곳에서 외계인의 침공을 견딜 수 있다. 그러나 시의 규정과 지역 건축 법규 때문에 대피소의 크기에는 제한이 있다. 따라서 정부는 UFO 함대가 태양을 가리는 드문 상황이 닥쳤을 때, 모든 시민이 침착하게 향할 대피소를 각자에게 배정해야 한다. 어느 대피소에도 정원보다 많은 사람을 배정하지 않는다는 조건 아래, 모든 사람이 대피소에 도착하는 데 걸리는 시간을 최소화하는 것이 가장 중요하다.

Louvain-la-Neuve를 사람이 사는 n개의 장소와, 이를 연결하는 m개의 양방향 도로로 이루어진 네트워크로 모델링한다. 도시 안 s개의 지점에 대피소가 있으며, 각 대피소에는 최대 수용 인원이 주어진다. 사람을 대피소에 최적으로 배정할 때, 모든 사람이 대피소에 도착하는 데 걸리는 최소 시간은 얼마인가?

Louvain-la-Neuve 시 정부는 시민을 수용할 대피소 용량이 충분하고, 모든 대피소가 어느 장소에서든 도달 가능하도록, 즉 항상 모든 사람을 어떤 식으로든 대피시킬 수 있도록 보장해 두었다.

• 첫째 줄에 세 정수, 장소의 수 $1 \le n \le 10^5$, 도로의 수 $0 \le m \le 2 \cdot 10^5$, 대피소의 수 $1 \le s \le 10$가 주어진다.
• 다음 줄에 $n$개의 정수 $0 \le p_i \le 10^9$가 주어지며, 장소 $1 \le i \le n$에 사는 사람의 수를 나타낸다.
• 다음 $m$개의 줄에 세 정수 $1 \le u, v \le n$과 $1 \le w \le 10^9$가 주어지며, $u$와 $v$를 연결하고 지나는 데 $w$의 시간이 걸리는 양방향 도로가 있음을 나타낸다. 임의의 두 장소를 직접 연결하는 도로는 최대 하나이며, 어떤 장소를 자기 자신과 연결하는 도로는 없다.
• 마지막으로 $s$개의 줄에 두 정수 $1 \le s_i \le n$과 $1 \le c_i \le 10^9$가 주어지며, 장소 $s_i$에 정원 $c_i$인 대피소가 있음을 나타낸다.

모든 사람이 대피하는 데 걸리는 최소 시간을 출력한다.