AT_abc369_g [ABC369G] As far as possible

给定一棵包含 $N$ 个顶点的树。顶点编号为 $1, 2, \ldots, N$。 第 $i$ 条边（$1\leq i\leq N-1$）连接顶点 $U_i$ 和顶点 $V_i$，长度为 $L_i$。 对于 $K=1,2,\ldots,N$，请解决以下问题。 > 高桥君和青木君进行一个游戏。游戏规则如下： > > - 首先，青木君在树上指定 $K$ 个互不相同的顶点。 > - 然后，高桥君需要构造一条起点和终点均为顶点 $1$ 的“步道”，并且该步道必须经过青木君指定的所有顶点。 > > 高桥君构造的步道的长度定义为分数。高桥君希望分数尽可能小，青木君希望分数尽可能大。请你求出当两人都采取最优策略时的分数。 步道的定义：在无向图（包括树）上，步道是指由 $k$ 个顶点（$k$ 为正整数）和 $k-1$ 条边交替组成的序列 $v_1,e_1,v_2,\ldots,v_{k-1},e_{k-1},v_k$，其中每条边 $e_i$ 连接顶点 $v_i$ 和 $v_{i+1}$。序列中同一个顶点或同一条边可以出现多次。步道经过顶点 $x$，是指存在 $1\leq i\leq k$ 使得 $v_i=x$（可以有多个这样的 $i$）。步道的起点和终点分别为 $v_1$ 和 $v_k$，步道的长度为 $e_1,e_2,\ldots,e_{k-1}$ 的长度之和。

输入以以下格式从标准输入读入。 > $N$ > $U_1$ $V_1$ $L_1$ > $U_2$ $V_2$ $L_2$ > $\vdots$ > $U_{N-1}$ $V_{N-1}$ $L_{N-1}$

输出 $N$ 行。第 $i$ 行（$1\leq i\leq N$）输出 $K=i$ 时问题的答案。

### 数据范围 - $2\leq N\leq 2\times 10^5$ - $1\leq U_i < V_i\leq N$ - $1\leq L_i\leq 10^9$ - 输入均为整数 - 给定的图为一棵树。 ### 样例解释 1 当 $K=1$ 时，青木君最优地指定顶点 $3$，此时高桥君可以构造步道 $1\to 2\to 3\to 2\to 1$，最优分数为 $16$。当 $K=2$ 时，青木君最优地指定顶点 $3,5$，此时高桥君可以构造步道 $1\to 5\to 1\to 2\to 3\to 2\to 1$ 等，最优分数为 $22$。当 $K\geq 3$ 时，双方最优时分数为 $26$。 ### 样例解释 2 注意答案可能超出 $32$ 位整数范围。 由 ChatGPT 4.1 翻译