휴가 계획

겨울 휴가 동안 적도 근처의 외딴 섬으로 함께 여행을 가려는 사람이 $p$명 있다. 모두 서로 다른 나라에 살고, 섬에는 비행기로만 갈 수 있다. 나라마다 공항은 하나뿐이라서 각자 자기 나라의 공항이 있는 도시까지 가야 한다. 일행은 모두 같은 날에 공항에 도착하기로 했고, 그날이 여행 첫날일 필요는 없다.

각 나라에는 도시가 $n$개, 일방통행 도로가 $m$개 있다. 도시 1이 집이 있는 도시이고, 도시 $a$에 공항이 있다. 0일째에 모든 사람은 자기 나라의 도시 1에 있다. 그다음부터는 하루마다 지금 있는 도시에서 도로 하나를 따라 다른 도시로 이동하거나, 지금 있는 도시에 머문다. 도시 $u$에서 도시 $v$로 가는 도로를 이용하면 비용 $g$를 내고, 도시 $v$에 머물면 그 도시에서 가장 싼 숙박비 $h_v$를 낸다. 매일 둘 중 하나를 반드시 고른다.

일행은 돈을 모아서 쓰기로 했으므로 계획도 함께 짠다. 같은 일수 $D$가 지난 시점에 모든 사람이 자기 나라의 공항 도시에 있어야 하고, $D$는 0일 수도 있다. 이때 드는 비용의 합이 가장 작은 값을 구하라.

도로에는 방향이 있고, $u$에서 $v$로 가는 비용과 $v$에서 $u$로 가는 비용이 같을 필요는 없다. 자기 자신으로 이어지는 도로는 없다. 모든 나라에는 도시 1에서 공항 도시로 가는 경로가 적어도 하나 있다.

그림 L.1. 두 사람의 나라 지도. 공항은 각각 도시 4와 도시 3에 있고, 집은 둘 다 도시 1이다. $g$는 도로 이동 비용, $h$는 가장 싼 숙박비를 뜻한다.

그림 L.1에서 가장 싼 계획은 다음과 같다. 1일째에 첫 번째 사람은 도시 3으로, 두 번째 사람은 도시 2로 이동한다. 2일째에 첫 번째 사람은 도시 4로, 두 번째 사람은 도시 1로 돌아간다. 3일째에 첫 번째 사람은 도시 4에 머물고, 두 번째 사람은 도시 3으로 이동한다. 비용은 $(1 + 5 + 1) + (3 + 2 + 4) = 16$이다.

첫째 줄에 일행의 인원이자 나라의 수인 정수 $p$가 주어진다 ($1 \le p \le 3$).

이어서 나라 $p$개의 정보가 차례로 주어진다. 각 나라의 첫째 줄에는 도시의 수 $n$과 도로의 수 $m$이 주어진다 ($1 \le n \le 50$, $n - 1 \le m \le 4n$). 다음 $n$개 줄에는 도시 1번부터 $n$번까지의 가장 싼 숙박비 $h$가 한 줄에 하나씩 순서대로 주어진다 ($0 \le h \le 1{,}000{,}000$). 다음 $m$개 줄에는 도로 정보가 정수 세 개 $u$, $v$, $g$로 주어진다 ($1 \le u, v \le n$, $u \ne v$, $0 \le g \le 1{,}000{,}000$). 도시 $u$에서 도시 $v$로 가는 일방통행 도로의 비용이 $g$라는 뜻이다. 각 나라의 마지막 줄에는 공항이 있는 도시의 번호 $a$가 주어진다 ($1 \le a \le n$). 모든 나라에서 집이 있는 도시는 1번이다.

모든 사람이 같은 일수가 지난 뒤 자기 나라의 공항 도시에 있도록 할 때 드는 비용의 합의 최솟값을 정수 하나로 한 줄에 출력한다.