Задачи
Башня карликов
Башня карликов
Маленький Вася играет в игру "Башня карликов". В этой игре имеются $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
Выведите одно число --- наименьшее количество потраченных денег.
Входные данные #1
5 3 5 0 1 2 5 5 2 3 4 2 3 1 4 5
Выходные данные #1
2
Входные данные #2
3 1 2 2 1 1 2 3
Выходные данные #2
2