Вежа гномів

Вхідні дані

Перший рядок містить два числа $n$ і $m$ ( $1 \leq n \leq 1 0^{4}$ 1 \le n \le 10^4, $0 \leq m \leq 1 0^{5}$ 0 \le m \le 10^5) — кількість різних предметів і число рецептів конструювання.

Другий рядок містить $n$ цілих чисел $c_{i}$ c_i ( $0 \leq c_{i} \leq 1 0^{9}$ 0 \le c_i \le 10^9) — вартості предметів.

Кожен з наступних $m$ рядків описує один рецепт. У кожному рядку записані три різних цілих числа $a_{i}, x_{i}, y_{i}$ a_i, x_i, y_i, де $a_{i}$ a_i — предмет, який можна сконструювати з предметів $x_{i}$ x_i та $y_{i}$ y_i ( $1 \leq a_{i}, x_{i}, y_{i} \leq n$ 1 \le a_i, x_i, y_i \le n, $a_{i} \neq = x_{i}$ a_i \ne x_i, $x_{i} \neq = y_{i}$ x_i \ne y_i, $y_{i} \neq = a_{i}$ y_i \ne a_i).

Вихідні дані

Виведіть одне число — мінімальну кількість грошей, яку необхідно витратити.

Приклади

Приклад 1

Loading

Приклад 2

Loading