신문 배달

등록금에 쪼들리는 학생인 당신은 신문 배달 아르바이트를 하기로 했습니다. 배달 구역으로 $1$번부터 $N$번까지 번호가 매겨진 주소들의 집합을 배정받았습니다.

매일 아침 당신은 신문사 사무실인 $0$번 주소에서 출발합니다. 모든 주소에 신문을 배달하는 경로를 짜야 하며, 배달을 마치면 곧바로 수업에 가고 싶습니다. 이 지역에는 주소들을 잇는 도로가 정확히 $N$개 있고, 각 도로를 지나는 데 걸리는 시간이 정해져 있습니다. 또한 신문사 사무실을 포함해 각 위치에서 캠퍼스까지 가는 데 걸리는 시간을 미리 계산해 두었습니다. 신문 배달을 끝내고 학교 자리에 앉기까지 걸리는 최소 시간은 얼마일까요?

첫째 줄에 정수 $N$(주소의 개수, $1 \le N \le 100000$)이 주어집니다.

다음 $N+1$개의 줄에는 각각 정수 $c_i$($i = 0, 1, \dots, N$, $0 \le c_i \le 1{,}000{,}000{,}000$)가 주어집니다. 위치 $i$에서 캠퍼스까지 가는 데 걸리는 시간입니다.

마지막 $N$개의 줄에는 각각 세 정수 $a$, $b$, $c$($0 \le a, b \le N$, $a \ne b$, $0 \le c \le 1{,}000$)가 주어지며, 위치 $a$와 $b$를 잇고 지나는 데 $c$분이 걸리는 도로를 나타냅니다.

모든 주소에 도달할 수 있음이 보장됩니다. (위치 $0$은 신문사 사무실임을 기억하세요.)

모든 신문을 배달하고 수업에 도착하기까지 걸리는 최소 시간을 출력합니다.

모든 주소를 방문한 뒤 사무실로 돌아와 거기서 학교로 가는 편이 더 나을 수도 있습니다.

예를 들어 $0 \to 1 \to 0 \to 2 \to 0 \to \text{학교}$ 경로는 $1 + 1 + 2 + 2 + 1 = 7$의 시간이 걸립니다.