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:
You can buy an item. The i-th item costs ci money.
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.
Help Vasya to spend the least amount of money to get the item number 1.
The first line contains two integers n and m (1≤n≤104,0≤m≤105) — the number of different items and the number of crafting types.
The second line contains n integers ci (0≤ci≤109) — values of the items.
The following m lines describe crafting types, each line contains three distinct integers ai,xi,yi, where ai is the item that can be crafted from items xi and yi (1≤ai,xi,yi≤n,ai=xi,xi=yi,yi=ai).
Print a single integer — the least amount of money to spend.