N. Сумма длин всех путей

На рёбрах дерева написаны веса. Посчитайте сумму длин всех путей: пути $\langle u, v \rangle$ и $\langle v, u \rangle$ считаются различными.

Путей $n(n-1)$, при $n = 10^5$ это $10^{10}$ - перебирать нельзя. Но каждое ребро можно посчитать отдельно.

В первой строке - число вершин $n$ ($1 \le n \le 10^5$).

В следующих $n-1$ строках - тройки $v$, $u$, $w$: ребро между $v$ и $u$ веса $w$ ($0 \le w \le 10^6$).

Выведите суммарную длину всех путей в дереве.