Задача №111886. Dwarf Tower
Вася играет в новую игру «Dwarf Tower». В этой игре есть \(n\) различных предметов, которые можно надеть на персонажа. Предметы пронумерованы с \(1\) по \(n\). Вася хочет получить предмет номер \(1\).
Есть два способа получить предмет.
- Предмет можно купить. Предмет номер \(i\) стоит \(c_i\) денег.
- Предмет можно сделать. Сейчас игра поддерживает \(m\) рецептов. Для того, чтобы сделать предмет, надо взять два определенных предмета и получить в результате нужный.
Помогите Васе потратить как можно меньше денег на предмет с номером \(1\).
Первая строка содержит два числа \(n\) и \(m\) (\(1 \leq n \leq 10000\), \(0\leq m\leq 100000\)) - количество предметов и количество рецептов.
Вторая строка содержит \(n\) чисел \(c_i\) - цены предметов (\(0\leq c_i \leq 10^9\)).
Следующие \(m\) строк содержат описания рецептов. Каждая строка содержит тройку различных чисел \(a_i\), \(x_i\), \(y_i\) – \(a_i\) это номер предмета, получаемого из предметов \(x_i\) и \(y_i\) (\(1 \leq a_i, x_i, y_i \leq n\)).
Выведите одно число – наименьшее количество денег, которое необходимо потратить.
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