Wind of Change

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 is labeled with a number $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)$ the same way.

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

Input

The first line contains a single integer $N$, the number of vertices in both trees. ($2 \le N \le 250\,000$)

The next $N-1$ lines describe the first tree. Each line contains three integers $S_i,\ E_i,\ W_i$, which means there is an edge connecting vertices $S_i$ and $E_i$ with weight $W_i$. ($1 \le S_i,\ E_i \le N,\ 1 \le W_i \le 10^9$)

The next $N-1$ lines describe the second tree in the same format.

Output

Print $N$ lines, each containing a single integer. The $i$-th line holds the answer for point $i$.