March 28 ADA University Students + Schoolchildren
Башня карликов
Маленький Вася играет в игру "Башня карликов". В этой игре имеются n различных предметов, которые Вы можете надеть на Вашего персонажа — карлика. Предметы пронумерованы от 1 до n. Вася хочет получить предмет номер 1.
Имеются два варианта получения предметов:
Вы можете купить предмет. i-ый предмет стоит c_i денег.
Вы можете сконструировать предмет. В игре имеется только m различных вариантов конструирования. Для получения нового предмета Вам следует отдать два различных предмета.
Помогите Васе потратить наименьшее количество денег для приобретения предмета номер 1.
Вхідні дані
Первая строка содержит два числа 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).
Вихідні дані
Выведите одно число — наименьшее количество потраченных денег.
Приклад
5 3 5 0 1 2 5 5 2 3 4 2 3 1 4 5
2
3 1 2 2 1 1 2 3
2