Smugglers

Memory limit: 32 MB

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' know-how 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 into a metal 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 that:
  • is gold,
  • for each the alchemists are able to obtain metal from metal , 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 , for ) 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, . In the -st line, for , there is a non-negative even integer : the price of 1 kg of the -th metal, . We assume that gold has the number 1. In the -nd line there is one non-negative integer equal to the number of transformation processes the alchemists are able to conduct, . In each of the following lines there are three positive integers, separated by single spaces, describing consecutive transformation processes. A triple of numbers , , denotes that the alchemists are able to obtain the -th metal from the -th metal, and they demand bytealers for transforming 1 kg of material, , . An ordered pair of numbers and 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 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 result is:

60

Task author: Lukasz Kowalik.