X Olympiad in Informatics 2002/2003

Problem: Smugglers

Author: Lukasz Kowalik

Byteotia is famous for its rich deposits of gold. Therefore, for
many years there flourished the sale of that metal to a neighbouring
kingdom, Bitland. Unfortunately, the growing deficit of the national
budget forced the king of Bitland to introduce heavy tariffs on metals
and minerals. Traders crossing the border have to pay customs duty of
50% of the value of the transported load. Byteotian merchants are
threatened with bankruptcy. Fortunately, Byteotian alchemists have
developed ways to transform some metals into other. The merchants'
idea is to use the alchemists' knowhow to transform gold into some
cheap metal, and next, after crossing the border and paying little
tariff, to transform it back into gold. Unfortunately, the alchemists
can not transform any metal into arbitrarily chosen other
one. Therefore, it may happen that the process of obtaining a given
metal from gold must be a chain of transformations that produces a
different metal on each stage. The alchemists demand stiff fees for
their services. They have fixed a price for transforming 1 kg of a
metal A into a metal B for each transformation they are
able to conduct. The traders ponder on what form gold should be
transported across the border and what sequence of alchemical
processes should be applied to achieve the highest income.
Task
Help to cure Byteotian economy! Write a program which:
 Reads a table of prices for all metals and prices for
transformations offered by the alchemists.
 Determines such a sequence of metals m_{1},
m_{1}, ..., m_{k} that:
 m_{1} = m_{k} is gold,
 for each i=2, 3, ..., k the alchemists are able to
obtain metal m_{i} from metal
m_{i1}, and
 the cost of performing the whole sequence of alchemical
processes for 1 kg of gold, augmented by the duty paid on the border
(50% of the price of 1 kg of the cheapest metal from
m_{i}, for i = 1, 2, ..., k) is
the smallest possible.
We assume that during the alchemical processes the weight of metals
does not alter.
 Writes out the cost of performing the determined
sequence of alchemical processes augmented by the duty paid on the
border.
Input
In the first line of the standard input there is one positive integer
n denoting the number of different metals, 1 <= n
<= 5000. In the (k+1)st line, for 1 <= k <=
n, there is a nonnegative even integer
p_{k}: the price of 1 kg of the kth
metal, 0 <= p_{k} <= 10^{9}. We
assume that gold has the number 1. In the (n+2)nd line there
is one nonnegative integer m equal to the number of
transformation processes the alchemists are able to conduct, 0 <=
m <= 100000. In each of the following m lines there
are three positive integers, separated by single spaces, describing
consecutive transformation processes. A triple of numbers a,
b, c denotes that the alchemists are able to obtain the
bth metal from the ath metal, and they demand c
bytealers for transforming 1 kg of material, 1 <= a,b
<= n, 0 <= c <= 10000. An ordered pair of numbers
a and b may appear at most once in the data.
Output
Your program should write to the standard output. In the first line
there should be one integer  the cost of performing the alchemical processes
determined by your program augmented by the duty paid on the border.
Example
For the following input data:
4
200
100
40
2
6
1 2 10
1 3 5
2 1 25
3 2 10
3 4 5
4 1 50
the correct answer is in the following output:
60