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

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

Дано дерево з вершин та n-1 ребер. -те ребро з'єднує вершини u_i та v_i, а також має вагу w_i. -та вершина також має значення x_i.

Нехай f(a, b) — відстань між вершинами та плюс x_a + x_b.

Хай буде повний граф , де вага ребра між вершинами та  — це f(a, b). Знайдіть вагу найменшого кістякового дерева.

Input

Перший рядок містить одне ціле число (2 \leq n \leq 200\,000).

Другий рядок містить цілих чисел 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).

Output

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

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading