Alchemist's Border Crossing

Byteotia is famous for its rich gold mines. Every year, a large amount of gold is traded along its border with Bitland. Unfortunately, due to heavy taxation, any merchant carrying minerals across the border must pay a tariff of 50\% of the mineral's market price.

Fortunately, some alchemists have invented methods to convert one type of mineral into another. This means that before crossing the border, a merchant can convert his expensive mineral (gold) into a cheaper one, pay a lower tariff based on the cheaper mineral's price, and then convert it back after crossing the border. However, each conversion method charges its own fee.

A merchant wants to carry 1 kg of gold across the border. He can perform an arbitrary number of conversions before and after crossing the border. When he crosses, he pays a tariff equal to 50\% \times (price\ of\ the\ mineral at border). Given the prices of different minerals and the conversion methods available, determine the minimum total cost incurred (conversion fees plus the tariff) to end up with 1 kg of gold on the other side.

Input/Output: Read the input from standard input and write the answer to standard output.

inputFormat

The first line contains an integer m indicating the number of different minerals.

Each of the next m lines contains a mineral name (a string without spaces) and its market price (a positive number), separated by a space. One of these minerals is named gold.

The following line contains an integer n indicating the number of conversion methods available.

Each of the next n lines contains a conversion description with three fields: source mineral, destination mineral, and the conversion fee (a non-negative number), all separated by spaces. The conversion is one‐way; that is, converting from A to B costs the given fee and converting back from B to A (if available) may have a different fee.

You may assume that all values are such that the answer can be represented using a double precision number.

outputFormat

Output a single number — the minimum total cost to transport 1 kg of gold across the border. The cost includes the sum of all conversion fees plus the tariff, which is computed as 0.5\times (price\ of\ the\ mineral at border). If no sequence of conversions exists to achieve the goal, output an appropriate message.

sample

1
gold 1000
0

500