eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

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

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

Пример

Входные данные #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
Источник 2013 ACM NEERC, Северный регион, Санкт Петербург, Октябрь 26