Маленький Вася играет в игру "Башня карликов". В этой игре имеются n различных предметов, которые Вы можете надеть на Вашего персонажа — карлика. Предметы пронумерованы от 1 до n. Вася хочет получить предмет номер 1.
Имеются два варианта получения предметов:
Вы можете купить предмет. i-ый предмет стоит ci денег.
Вы можете сконструировать предмет. В игре имеется только m различных вариантов конструирования. Для получения нового предмета Вам следует отдать два различных предмета.
Помогите Васе потратить наименьшее количество денег для приобретения предмета номер 1.
Первая строка содержит два числа n и m (1≤n≤104,0≤m≤105) — количество различных предметов и число конструирований.
Вторая строка содержит n целых чисел ci (0≤ci≤109) — стоимости предметов.
Следующие m строк описывают преобразования предметов, каждая строка содержит три различных целых числа ai,xi,yi, где ai предмет, который можно сконструировать из xi и yi (1≤ai,xi,yi≤n,ai=xi,xi=yi,yi=ai).
Выведите одно число — наименьшее количество потраченных денег.