밀수꾼

바이트오티아(Byteotia)는 풍부한 금 매장량으로 유명하다. 오랫동안 이웃 왕국 비트랜드(Bitland)에 금을 팔아 왔지만, 비트랜드 국왕은 재정 적자 때문에 금속과 광물에 높은 관세를 매기기 시작했다. 국경을 넘는 상인은 운반하는 화물 가치의 50%를 관세로 내야 한다.

다행히 바이트오티아의 연금술사들은 어떤 금속을 다른 금속으로 바꾸는 방법을 개발했다. 상인들의 아이디어는 금을 값싼 금속으로 바꾼 뒤 국경을 넘어 적은 관세만 내고, 국경을 넘은 다음 다시 금으로 되돌리는 것이다. 그러나 연금술사가 임의의 금속을 원하는 다른 금속으로 곧바로 바꿀 수 있는 것은 아니다. 따라서 금에서 특정 금속을 얻으려면, 매 단계마다 서로 다른 금속을 거치는 변환의 사슬이 필요할 수도 있다. 연금술사는 자신이 수행할 수 있는 각 변환마다 금속 A 1 kg을 금속 B로 바꾸는 값을 미리 정해 두고 비싼 수수료를 요구한다.

금은 1번 금속이다. 다음을 만족하는 금속의 순서 $m_0, m_1, \dots, m_k$ 를 정하려 한다.

• $m_0 = m_k$ 는 금(1번 금속)이다.
• 각 $i = 1, 2, \dots, k$ 에 대해 연금술사는 금속 $m_{i-1}$ 로부터 금속 $m_i$ 를 얻을 수 있다.
• 1 kg의 금에 대해 이 변환 전체를 수행하는 비용에, 국경에서 내는 관세를 더한 값이 최소가 된다. 이때 관세는 순서에 등장하는 금속 $m_i$ (단 $i = 0, 1, \dots, k$) 중 가장 값싼 금속 1 kg 가격의 50%이다.

연금술 변환 도중 금속의 무게는 변하지 않는다고 가정한다.

정한 변환 순서를 수행하는 비용에 국경에서 낸 관세를 더한 값을 출력하여라.

첫째 줄에 서로 다른 금속의 수를 나타내는 양의 정수 $n$ 이 주어진다 ($1 \le n \le 5\,000$). 이어서 $k+1$번째 줄($1 \le k \le n$)에는 $k$번 금속 1 kg의 가격을 나타내는, 음이 아닌 짝수 $p_k$ 가 주어진다 ($0 \le p_k \le 10^9$). 금은 1번 금속이다. $n+2$번째 줄에는 연금술사가 수행할 수 있는 변환의 수 $m$ 이 주어진다 ($0 \le m \le 100\,000$). 이어지는 $m$개의 줄에는 각각 공백으로 구분된 세 정수 $a$, $b$, $c$ 가 주어진다. 이는 연금술사가 $a$번 금속으로부터 $b$번 금속을 얻을 수 있고, 그 1 kg을 변환하는 데 $c$ 바이트알러를 요구함을 뜻한다 ($1 \le a, b \le n$, $0 \le c \le 10\,000$). 정렬된 쌍 $(a, b)$ 는 입력에 많아야 한 번 나타난다.

첫째 줄에 정수 하나를 출력한다. 이는 프로그램이 정한 연금술 변환을 수행하는 비용에 국경에서 낸 관세를 더한 값이다.