Matching on Tree Distance Graph

This problem is dedicated to current ICPC champions, from one of the 2020 ICPC champions and, hopefully, the 2023 champions, to the 2021 champions and, hopefully, the 2022 champions, with love.

You are given an edge-weighted tree $T$ on $n$ vertices. Define $d_{uv}$ as the sum of weights on the only simple path between $u$ and $v$ in $T$. Consider a full weighted graph $G$, where the weight of the edge $(u, v)$ is $d_{uv}$.

For every $k$ between $1$ and $\lfloor n/2 \rfloor$, calculate the maximum possible weight of a matching of size $k$ in graph $G$. A matching of size $k$ is a set of $k$ edges such that no two edges in this set share a vertex.

The first line contains one integer $n$ ($2 \le n \le 100\,000$), the size of the tree.

The next $n-1$ lines describe the edges of the tree. The $i$-th of them contains three integers $u_i$, $v_i$, $w_i$ ($1 \le u_i, v_i \le n$, $1 \le w_i \le 10^8$), meaning that there is an edge $(u_i, v_i)$ with weight $w_i$ in $T$.

It is guaranteed that the given edges form a tree.

Print $\lfloor n/2 \rfloor$ integers, the maximum weights of matchings of the corresponding sizes in $G$.