Score : $600$ points

问题陈述

你得到了一个有 $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$ 开始并在顶点 $1$ 结束的路径，并且通过青木指定的所有顶点。

分数定义为高桥构建的路径的长度。高桥想要最小化分数，而青木想要最大化它。当两个玩家都以最优方式玩时，找出分数。

路径的定义 在无向图（可能是树）上的路径是一系列 $k$ 个顶点和 $k-1$ 条边 $v_1,e_1,v_2,\ldots,v_{k-1},e_{k-1},v_k$（其中 $k$ 是一个正整数），使得边 $e_i$ 连接顶点 $v_i$ 和 $v_{i+1}$。同一个顶点或边可以在序列中多次出现。如果存在至少一个 $i$（$1\leq i\leq k$）使得 $v_i=x$，则路径通过顶点 $x$。（可以有多个这样的 $i$。）路径分别从 $v_1$ 开始并在 $v_k$ 结束，路径的长度是 $e_1$, $e_2$, $\ldots$, $e_{k-1}$ 的长度之和。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given a tree with $N$ vertices. The vertices are numbered $1$, $2$, $\ldots$, $N$.
The $i$-th edge ($1\leq i\leq N-1$) connects vertices $U_i$ and $V_i$, with a length of $L_i$.

For each $K=1,2,\ldots, N$, solve the following problem.

Takahashi and Aoki play a game. The game proceeds as follows.

• First, Aoki specifies $K$ distinct vertices on the tree.
• Then, Takahashi constructs a walk that starts and ends at vertex $1$, and passes through all the vertices specified by Aoki.

The score is defined as the length of the walk constructed by Takahashi. Takahashi wants to minimize the score, while Aoki wants to maximize it. Find the score when both players play optimally.

Definition of a walk A walk on an undirected graph (possibly a tree) is a sequence of $k$ vertices and $k-1$ edges $v_1,e_1,v_2,\ldots,v_{k-1},e_{k-1},v_k$ (where $k$ is a positive integer) such that edge $e_i$ connects vertices $v_i$ and $v_{i+1}$. The same vertex or edge can appear multiple times in the sequence. A walk is said to pass through vertex $x$ if there exists at least one $i$ ($1\leq i\leq k$) such that $v_i=x$. (There can be multiple such $i$.) The walk is said to start and end at $v_1$ and $v_k$, respectively, and the length of the walk is the sum of the lengths of $e_1$, $e_2$, $\ldots$, $e_{k-1}$.

Constraints

• $2\leq N\leq 2\times 10^5$
• $1\leq U_i<V_i\leq N$
• $1\leq L_i\leq 10^9$
• All input values are integers.
• The given graph is a tree.

Input

The input is given from Standard Input in the following format:

$N$

$U_1$ $V_1$ $L_1$

$U_2$ $V_2$ $L_2$

$\vdots$

$U_{N-1}$ $V_{N-1}$ $L_{N-1}$

Output

Print $N$ lines. The $i$-th line $(1\leq i\leq N)$ should contain the answer to the problem for $K=i$.

Sample Input 1

5
1 2 3
2 3 5
2 4 2
1 5 3

Sample Output 1

16
22
26
26
26

For $K=1$, Aoki's optimal move is to specify vertex $3$, and Takahashi's optimal move is to construct a path vertex $1$ $\to$ vertex $2$ $\to$ vertex $3$ $\to$ vertex $2$ $\to$ vertex $1$, resulting in a score of $16$.

For $K=2$, Aoki's optimal move is to specify vertices $3$ and $5$, and Takahashi's optimal move is to construct a path such as vertex $1$ $\to$ vertex $5$ $\to$ vertex $1$ $\to$ vertex $2$ $\to$ vertex $3$ $\to$ vertex $2$ $\to$ vertex $1$, resulting in a score of $22$.

For $K\geq 3$, the score when both players play optimally is $26$.

Sample Input 2

3
1 2 1000000000
2 3 1000000000

Sample Output 2

4000000000
4000000000
4000000000

Beware that the answer may not fit in a $32$-bit integer.