Dwarf Tower#6263
Little Vasya is playing a game called "Dwarf Tower". In this game, there are different items that can be equipped on a character — a dwarf. All items are numbered from to . Vasya wants to obtain item number .
There are two ways to obtain items:
Buy an item: the -th item costs c_i coins.
Craft an item: there are different crafting recipes in the game. To craft a new item, you need to give two other distinct items.
Help Vasya spend as little money as possible to get item number .
The first line contains two integers and m~(1 \le n \le 10^4, 0 \le m \le 10^5) — the number of different items and the number of crafting recipes.
The second line contains integers c_i~(0 \le c_i \le 10^9) — the costs of the items.
Each of the following lines describes a recipe. 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).
Print one integer — the minimum amount of money that needs to be spent.
Example 1
Example 2