Item Crafting

Sunyoung recently started a game called "Norris Tower". The game has $n$ kinds of items, and her character can wear every one of them. The items are numbered 1 through $n$. Sunyoung wants to obtain item 1.

There are two ways to obtain an item.

• She can buy the item. Item $i$ costs $c_i$ won.
• She can craft the item. There are $m$ crafting recipes in total. If she brings two items of different kinds to the blacksmith, the blacksmith makes the resulting item for free. The two items she hands over are not returned, so using the same kind twice means preparing two of them.

Write a program that computes the smallest amount of money Sunyoung needs to obtain item 1.

The first line contains the number of item kinds $n$ and the number of crafting recipes $m$. ($1 \le n \le 10\,000$, $0 \le m \le 100\,000$)

The second line contains the prices $c_1, c_2, \dots, c_n$ in increasing order of item number. ($0 \le c_i \le 10^9$)

Each of the next $m$ lines contains one recipe as the result item and the two ingredient items, $a_i$, $x_i$, $y_i$, in that order. Handing one item $x_i$ and one item $y_i$ to the blacksmith yields item $a_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$)

Print, on one line, the smallest amount of money needed to obtain item 1.