Башня карликов

Маленький Вася играет в игру "Башня карликов". В этой игре имеются $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)$.

Выходные данные

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

Примеры