P8385 [POI 2003] Smugglers

Byteotia is famous around the world for its rich gold resources. Therefore, every year there are a lot of gold trades on the border with its neighboring country Bitland. Unfortunately, because taxes are very heavy, merchants must pay $50\%$ of the mineral’s price as customs duty when carrying minerals across the border. Luckily, some alchemists have invented methods to convert one kind of metal mineral into another. In this way, during trading, one can first convert an expensive mineral into a cheaper one, and after crossing the border, convert it back. However, since this work is time-consuming and laborious, the alchemists charge a corresponding fee for each conversion. Now a merchant wants to carry $1$ kg of gold across the border, and he wants to know what the minimum total cost is.

The first line contains a single integer $n$, the number of kinds of metal minerals. The next $n$ lines give the unit price of $1$ kg for each metal. The number $p_k$ on line $k+1$ is the unit price of the $k$-th metal. We assume that gold has index $1$. Next comes a positive integer $m$, meaning there are $m$ conversion methods. The next $m$ lines each describe one conversion with three numbers $a$, $b$, $c$, meaning converting $1$ kg of metal $a$ into $1$ kg of metal $b$ costs $c$. For any specific pair of metals $a$ and $b$, it appears at most once.

Output one line: the minimum total cost to carry $1$ kg of gold across the border.

Constraints: for $100\%$ of the testdata, $1 \le n \le 5000$, $0 \le p_k \le 10^9$, $0 \le m \le 100000$, $1 \le a,b \le n$, $0 \le c \leq 10000$. Translated by ChatGPT 5