Маленький Вася играет в игру "Башня карликов". В этой игре имеются $n$ различных предметов, которые Вы можете надеть на Вашего персонажа --- карлика. Предметы пронумерованы от $1$ до $n$. Вася хочет получить предмет номер $1$. Имеются два варианта получения предметов: \begin{itemize} \item Вы можете купить предмет. $i$-ый предмет стоит $c_i$ денег. \item Вы можете сконструировать предмет. В игре имеется только $m$ различных вариантов конструирования. Для получения нового предмета Вам следует отдать два различных предмета. \end{itemize} Помогите Васе потратить наименьшее количество денег для приобретения предмета номер $1$. \InputFile Первая строка содержит два числа $n$ и $m~(1 \le n ≤ 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)$. \OutputFile Выведите одно число --- наименьшее количество потраченных денег.