Wind of Change

이 문제의 원래 제목은 "Tree Product Metric Voronoi Diagram Query Without One Point"이다.

크기 $N$인 두 가중치 트리 $T_1,\ T_2$가 주어지며, 각 정점에는 $1 \ldots N$의 번호가 붙어 있다. $dist(T_1,\ i,\ j)$를 트리 $T_1$에서 노드 $i$에서 $j$로 가는 최단 경로의 가중치 합으로 정의하고, $dist(T_2,\ i,\ j)$도 같은 방식으로 정의하자.

크기 $N$인 점 집합을 생각하자. 맨해튼 거리와 비슷하게(실제로 이는 그 일반화이다), 두 점 $1 \le i,\ j \le N$ 사이의 거리를 두 거리의 합 $dist(T_1,\ i,\ j) + dist(T_2,\ i,\ j)$로 정의할 수 있다. 각 $1 \le i \le N$에 대해 점 $i$에서 가장 가까운 점을 구하자. 즉, 각 $i$에 대해 $min_{j \neq i}{dist(T_1,\ i,\ j) + dist(T_2,\ i,\ j)}$를 구해야 한다.

입력

첫 줄에 두 트리의 정점 수를 나타내는 정수 $N$이 주어진다. ($2 \le N \le 250\,000$)

다음 $N-1$개의 줄에는 첫 번째 트리의 정보가 주어진다. 각 줄에는 세 정수 $S_i,\ E_i,\ W_i$가 주어지며, 이는 두 정점 $S_i,\ E_i$를 잇는 가중치 $W_i$의 간선이 있음을 나타낸다. ($1 \le S_i,\ E_i \le N,\ 1 \le W_i \le 10^9$)

그다음 $N-1$개의 줄에는 두 번째 트리의 정보가 같은 형식으로 주어진다.

출력

$N$개의 줄을 출력한다. 각 줄에는 정수 하나가 들어간다. $i$번째 줄에는 점 $i$에 대한 답을 출력한다.