题目描述

The original title of this problem is "Tree Product Metric Voronoi Diagram Query Without One Point".

You are given two weighted trees $T_1,\ T_2$ of size $N$, where each vertex are labeled with numbers $1 \ldots N$. Let $dist(T_1,\ i,\ j)$ be the total weight of the shortest path from node $i$ to $j$ in tree $T_1$, and define $dist(T_2,\ i,\ j)$ similarly.

Consider a point set of size $N$. Similar to Manhattan metric (in fact, this is a generalization of it), we can define the distance between two points $1 \le i,\ j \le N$: It is the sum of two distances, $dist(T_1,\ i,\ j) + dist(T_2,\ i,\ j)$. For each $1 \le i \le N$, please determine the "closest point" from the point $i$. Formally, for each $i$, you should find $\min_{j \neq i}{dist(T_1,\ i,\ j) + dist(T_2,\ i,\ j)}$.

输入格式

In the first line, a single integer $N$ denoting the number of vertices in both trees is given. ($2 \le N \le 250\,000$)

In the next $N-1$ lines, description of the first tree is given. Each of the $N-1$ lines contains three integers $S_i, E_i, W_i$, which indicates there is an edge connecting two vertices $S_i, E_i$ with weight $W_i$ ($1 \le S_i, E_i \le N, 1 \le W_i \le 10^9$)

In the next $N-1$ lines, description of the second tree is given in the same format.

输出格式

Print $N$ lines containing a single integer. In the $i$-th line, you should print a single integer denoting the answer for the point $i$.

5
1 2 10
2 4 20
3 4 30
4 5 50
1 2 15
1 3 25
1 4 35
1 5 25

25
25
85
65
105

9
5 7 6577
4 5 8869
5 9 9088
2 1 124
6 2 410
2 8 8154
4 8 4810
3 4 4268
3 9 763
6 2 8959
7 4 7984
3 8 504
8 6 9085
5 2 4861
1 9 8539
1 7 7834

18084
9369
9582
23430
26694
9369
23430
9582
22988