eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Маленький Вася играет в игру "Башня карликов". В этой игре имеются n различных предметов, которые Вы можете надеть на Вашего персонажа — карлика. Предметы пронумерованы от 1 до n. Вася хочет получить предмет номер 1.

Имеются два варианта получения предметов:

  • Вы можете купить предмет. i-ый предмет стоит c_i денег.

  • Вы можете сконструировать предмет. В игре имеется только m различных вариантов конструирования. Для получения нового предмета Вам следует отдать два различных предмета.

Помогите Васе потратить наименьшее количество денег для приобретения предмета номер 1.

Giriş verilənləri

Первая строка содержит два числа 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).

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
5 3
5 0 1 2 5
5 2 3
4 2 3
1 4 5
Çıxış verilənləri #1
2
Giriş verilənləri #2
3 1
2 2 1
1 2 3
Çıxış verilənləri #2
2
Mənbə 2013 ACM NEERC, Северный регион, Санкт Петербург, Октябрь 26