e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.

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

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

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

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

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

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

Первая строка содержит два числа n и m (1n10000, 0m100000) - количество различных предметов и число конструирований.

Вторая строка содержит n целых чисел ci (0ci109) - стоимости предметов.

Следующие m строк описывают преобразования предметов, каждая строка содержит три различных целых числа ai, xi, yi - ai предмет, который можно сконструировать из xi и yi (1ai, xi, yin, aixi, xiyi, yiai).

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

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

Лимит времени 1 секунды
Лимит использования памяти 128 MiB
Входные данные #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, Northern Subregional Contest, St Petersburg, October 26