给定两棵带权树 $T_1, T_2$，它们各有 $N$ 个顶点，顶点编号均为 $1 \dots 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$ 的答案。

样例

样例输入 1

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

样例输出 1

25
25
85
65
105

样例输入 2

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

样例输出 2

18084
9369
9582
23430
26694
9369
23430
9582
22988