Дано дерево з $n$ вершин та $n-1$ ребер. $i$-те ребро з'єднує вершини $u_i$ та $v_i$, а також має вагу $w_i$. $i$-та вершина також має значення $x_i$. Нехай $f(a, b)$~--- відстань між вершинами $a$ та $b$ плюс $x_a + x_b$. Хай буде повний граф $G$, де вага ребра між вершинами $a$ та $b$~--- це $f(a, b)$. Знайдіть вагу найменшого кістякового дерева. \InputFile Перший рядок містить одне ціле число $n$ ($2 \leq n \leq 200\,000$). Другий рядок містить $n$ цілих чисел $x_1, x_2, \dots, x_n$ ($1 \leq x_i \leq 10^9$). Кожен з наступних $n-1$ рядків містить три цілі числа $u_i$, $v_i$ та $w_i$ ($1 \leq u_i, v_i \leq n$, $1 \leq w_i \leq 10^9$). \OutputFile Виведіть одне ціле число~--- відповідь на задачу.