Dwarf Tower

Little Vasya is playing a new game named "Dwarf Tower". In this game there are \( n \) different items, numbered from \(1\) to \(n\). Vasya wants to obtain the item with number \(1\). There are two ways to obtain an item:

• You can buy an item. The \(i\)-th item costs \(c_i\) money.
• You can craft an item. The game supports only \(m\) types of crafting. To craft an item, you give two particular different items and get another one as a result.

Your task is to help Vasya spend the least amount of money to eventually get item \(1\). Items obtained (bought or crafted) remain available for further crafting (i.e. they are not consumed). You may buy any items and use any crafting rules any number of times.

Input and output format: The first line contains two integers \(n\) and \(m\). The second line contains \(n\) integers: \(c_1, c_2, \ldots, c_n\), where \(c_i\) is the cost to buy item \(i\). Then \(m\) lines follow, each containing three integers \(a\), \(b\) and \(k\) (with \(a \neq b\)), which means that if you have items \(a\) and \(b\) (order does not matter) then you can craft item \(k\) at no extra cost.

Output the minimum amount of money Vasya needs to spend in order to get item \(1\).

inputFormat

The first line contains two integers \(n\) and \(m\) separated by a space.

The second line contains \(n\) integers \(c_1, c_2, \ldots, c_n\) separated by spaces.

Then \(m\) lines follow. Each of these lines contains three integers: \(a\), \(b\), and \(k\), indicating that if you have items \(a\) and \(b\), you can craft item \(k\>.

outputFormat

Output a single integer: the minimum amount of money required to obtain item \(1\).

sample

3 1
10 5 1
2 3 1

6