Вежа карликів

Маленький Вася грає в гру "Вежа гномів". У цій грі є $n$ різних предметів, які можна одягнути на вашого персонажа — гнома. Предмети пронумеровані від $1$ до $n$. Вася хоче отримати предмет номер $1$.

Є два способи отримання предметів:

• Ви можете купити предмет. $i$-ий предмет коштує $c_i$ грошей.

• Ви можете сконструювати предмет. У грі є лише $m$ різних варіантів конструювання. Для отримання нового предмета потрібно віддати два різних предмети.

Допоможіть Васі витратити найменшу кількість грошей для придбання предмета номер $1$.

Вхідні дані

Перший рядок містить два числа $n$ і $m(1\le n\le 10^4,0\le m\le 10^5)$ — кількість різних предметів і число конструювань.

Другий рядок містить $n$ цілих чисел $c_i(0\le c_i\le 10^9)$ — вартості предметів.

Наступні $m$ рядків описують перетворення предметів, кожен рядок містить три різних цілих числа $a_i,x_i,y_i$, де $a_i$ — предмет, який можна сконструювати з $x_i$ і $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)$.

Вихідні дані

Виведіть одне число — найменшу кількість витрачених грошей.

Приклади