Smugglers

Byteotia is famous for its rich deposits of gold. For many years it sold that metal to a neighbouring kingdom, Bitland. Unfortunately, a growing budget deficit forced the king of Bitland to impose heavy tariffs on metals and minerals: any trader crossing the border must pay a customs duty of 50% of the value of the transported load.

Fortunately, Byteotian alchemists have found ways to turn one metal into another. The merchants' idea is to turn gold into some cheap metal, cross the border paying only a small tariff, and then turn it back into gold. However, the alchemists cannot turn an arbitrary metal directly into any other one, so obtaining a given metal from gold may require a chain of transformations that passes through a different metal at each stage. For every transformation they can perform, the alchemists fix a price for converting 1 kg of a metal A into a metal B, and they charge stiff fees.

Gold is metal number 1. We look for a sequence of metals $m_0, m_1, \dots, m_k$ such that:

• $m_0 = m_k$ is gold (metal 1);
• for each $i = 1, 2, \dots, k$ the alchemists can obtain metal $m_i$ from metal $m_{i-1}$;
• the cost of performing the whole sequence of transformations on 1 kg of gold, plus the border duty, is as small as possible. Here the duty is 50% of the price of 1 kg of the cheapest metal among $m_i$ for $i = 0, 1, \dots, k$.

Assume that the weight of the metal does not change during the alchemical processes.

Output the cost of performing the chosen sequence of transformations plus the duty paid at the border.

The first line contains one positive integer $n$, the number of distinct metals ($1 \le n \le 5\,000$). For $1 \le k \le n$, line $k+1$ contains a non-negative even integer $p_k$, the price of 1 kg of the $k$-th metal ($0 \le p_k \le 10^9$). Gold is metal number 1. Line $n+2$ contains one non-negative integer $m$, the number of transformations the alchemists can perform ($0 \le m \le 100\,000$). Each of the next $m$ lines contains three integers $a$, $b$, $c$ separated by single spaces: the alchemists can obtain metal $b$ from metal $a$ and charge $c$ bytealers to convert 1 kg of it ($1 \le a, b \le n$, $0 \le c \le 10\,000$). Each ordered pair $(a, b)$ appears in the input at most once.

Output a single integer: the cost of performing the transformations chosen by your program, plus the duty paid at the border.