Маленький Василь грає в гру "Башта гномів". В цій грі є \(N\) різних предметів, які ви можете надягнути на вашого персонажа - гнома.
Предмети пронумеровані від \(1\) до \(N\). Василь хоче отримати предмет номер \(1\)

Існує два способи отримання предметів:

• Ви можете купити предмет.
  
• Ви можете створити предмет. В грі є \(M\) варіантів створення. Для отримання нового предмета вам необхідно віддати два різних предмени.
  

Допоможіть Василю витратити найменше грошей для отримання предмету номер \(1\)

Формат вхідних даних

Перший рядок містить два цілих числа \(N,M\) (\(1 \le N \le 10000\), \(0 \le M \le 100000\)) - кількість видів предметів і кількість варіантів створення.

Другий рядок містить \(N\) цілих чисел \(Ci\) - вартості предметів (\(0 \le Ci \le 10^9\))

Наступні \(M\) рядків описують створення предметів, кожен рядок містить три різних цілих числа \(T,X,Y\) - що означає, предмет \(T\) можна створити з предметів \(X\) та \(Y\)

Формат вихідних даних

Виведіть єдине число - найменшу кількість витрачених грошей.

Приклад вхідних даних-1

5 3
5 0 1 2 5
5 2 3
4 2 3
1 4 5

Приклад вихідних даних-1

2

Пояснення до прикладу-1

Спочатку купляємо предмети 2 та 3 - це буде коштувати 0+1=1
Далі з них створюємо предмет номер 5
Знову купляємо предмети 2 та 3 - це буде коштувати 0+1=1
Далі з них створюємо предмет номер 4
Тепер з предмету номе 5 та предмету номер 4 створюємо предмет номер 1
Загальні витрати: 1+1=2

Приклад вхідних даних-2

3 1
2 2 1
1 2 3

Приклад вихідних даних-2

2