D. Сумма длин путей

Дано дерево, на рёбрах написаны веса. Для каждой вершины посчитайте сумму взвешенных расстояний до всех остальных вершин.

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

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

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

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