Дано дерево з n вершин та n−1 ребер. i-те ребро з'єднує вершини ui та vi, а також має вагу wi. i-та вершина також має значення xi.
Нехай f(a,b) — відстань між вершинами a та b плюс xa+xb.
Хай буде повний граф G, де вага ребра між вершинами a та b — це f(a,b). Знайдіть вагу найменшого кістякового дерева.
Перший рядок містить одне ціле число n (2≤n≤200000).
Другий рядок містить n цілих чисел x1,x2,…,xn (1≤xi≤109).
Кожен з наступних n−1 рядків містить три цілі числа ui, vi та wi (1≤ui,vi≤n, 1≤wi≤109).
Виведіть одне ціле число — відповідь на задачу.