Little Vasya is playing a new game named "Dwarf Tower". In this game there are $n$ different items, which you can put on your dwarf character. Items are numbered from $1$ to $n$. Vasya wants to get the item with number $1$. There are two ways to obtain an item: \begin{itemize} \item You can buy an item. The $i$-th item costs $c_i$ money. \item You can craft an item. This game supports only $m$ types of crafting. To craft an item, you give two particular different items and get another one as a result. \end{itemize} Help Vasya to spend the least amount of money to get the item number $1$. \InputFile The first line contains two integers $n$ and $m~(1 \le n ≤ 10^4, 0 \le m \le 10^5)$ --- the number of different items and the number of crafting types. The second line contains $n$ integers $c_i~(0 \le c_i \le 10^9)$ --- values of the items. The following $m$ lines describe crafting types, each line contains three distinct integers $a_i, x_i, y_i$, where $a_i$ is the item that can be crafted from items $x_i$ and $y_i~(1 \le a_i, x_i, y_i \le n, a_i \ne x_i, x_i \ne y_i, y_i \ne a_i)$. \OutputFile Print a single integer --- the least amount of money to spend.