O. Сумма длин путей из каждой вершины

То же дерево, но теперь для каждой вершины $v$ нужна сумма расстояний от неё до всех остальных.

Считать $n$ раз обходом - это $O(n^2)$. Правильный приём называется сменой корня и стоит два обхода.

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

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

Выведите $n$ чисел: для каждой вершины сумму расстояний до всех остальных.