Дано дерево з вершин та ребер. -те ребро з'єднує вершини та , а також має вагу . -та вершина також має значення .
Нехай — відстань між вершинами та плюс .
Хай буде повний граф , де вага ребра між вершинами та — це . Знайдіть вагу найменшого кістякового дерева.
Перший рядок містить одне ціле число ().
Другий рядок містить цілих чисел ().
Кожен з наступних рядків містить три цілі числа , та (, ).
Виведіть одне ціле число — відповідь на задачу.