Кістякове дерево#10754
Дано дерево з вершин та n-1 ребер. -те ребро з'єднує вершини u_i та v_i, а також має вагу w_i. -та вершина також має значення x_i.
Нехай f(a, b) — відстань між вершинами та плюс x_a + x_b.
Хай буде повний граф , де вага ребра між вершинами та — це f(a, b). Знайдіть вагу найменшого кістякового дерева.
Перший рядок містить одне ціле число (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).
Виведіть одне ціле число — відповідь на задачу.
Приклад 1
Приклад 2
Приклад 3