Сума відстаней

Задано зважене дерево з $n$ вершин і $n-1$ ребер. Відстанню між вершинами $u$ і $v$ вважатимемо вагу найменшого ребра на шляху між $u$ і $v$.

Знайдіть суму відстаней між усіма парами вершин у дереві.

Вхідні дані

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

Вихідні дані

Виведіть суму відстаней між усіма парами вершин у дереві.

Приклади