Description

本题的原标题是“无一点树乘积度量 Voronoi 图查询”。

给定两个大小为 $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)}$。

Input Format

第一行给出一个整数 $N$，表示两棵树中的顶点数（$2 \le N \le 250,000$）。

接下来的 $N-1$ 行给出第一棵树的描述。这 $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$ 行以相同格式给出第二棵树的描述。

Output Format

输出 $N$ 行，每行包含一个整数。在第 $i$ 行，你应输出一个整数表示点 $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

Hint

翻译由 DeepSeek V3 完成