Кістякове дерево

Дано дерево з $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)$. Знайдіть вагу найменшого кістякового дерева.

Input

Перший рядок містить одне ціле число $n$ ($2\le n\le 200000$).

Другий рядок містить $n$ цілих чисел $x_1,x_2,\dots ,x_n$ ($1\le x_i\le 10^9$).

Кожен з наступних $n-1$ рядків містить три цілі числа $u_i$, $v_i$ та $w_i$ ($1\le u_i,v_i\le n$, $1\le w_i\le 10^9$).

Output

Виведіть одне ціле число — відповідь на задачу.

Examples