2022 年上海市大学生程序设计竞赛 - 十一月赛

E. Tree

A tree is a connected undirected graph without cycles. A weighted tree has a weight assigned to each edge. The distance between two vertices is the minimum sum of weights on the path connecting them.

Cuber QQ has two weighted trees $T_1$ and $T_2$, both two trees contain $n$ vertices. Denote $d(T, i, j)$ as the distance between vertex $i$ and vertex $j$ in tree $T$.

Cuber QQ proposes a new distance, Two-Tree Distance (TTD), where $\text{TTD}(i,j)=d(T_1, i, j)+d(T_2, i, j)$.

Now, for each vertex $i$, Cuber QQ wants to find the nearest vertex $j$, i.e., $j=\text{arg} \text{min}_{j^{‘}\neq i} \text{TTD}(i,j^{‘})$ and then output $\text{TTD}(i,j)$.

输入格式

The first line contains a single integer $n$ ($2\le n\le 10^5$).

Each of the next $n-1$ lines contains three integers $u,v$ and $w$ ($1\le u,v\le n,u\neq v,1\le w\le 10^9$), indicating that there is an edge between vertices $u$ and $v$ with wright of $w$ in $T_1$. It is guaranteed that the given edges form a tree.

Each of the next $n-1$ lines contains three integers $u,v$ and $w$ ($1\le u,v\le n,u\neq v,1\le w\le 10^9$), indicating that there is an edge between vertices $u$ and $v$ with wright of $w$ in $T_2$. It is guaranteed that the given edges form a tree.

输出格式

The output contains $n$ lines, in $i$-th line, a single integer indicates the minimized Two-Tree Distance of vertex $i$.

样例

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

Output
3
3
9
7
11


NaN