Сума відстаней#10761
Задано зважене дерево з вершин і n - 1 ребер. Відстанню між вершинами і вважатимемо вагу найменшого ребра на шляху між і .
Знайдіть суму відстаней між усіма парами вершин у дереві.
Перший рядок містить кількість вершин у графі n~(2 \le n \le 10^5). Наступні n - 1 рядків описують ребра. Кожен рядок містить три цілі числа: номери вершин, з'єднаних ребром (вершини пронумеровані від до ), і вагу ребра.
Виведіть суму відстаней між усіма парами вершин у дереві.
Приклад 1
Приклад 2