Minseok 和 Martin 有两棵带权树 $T_1, T_2$。它们共享大小为 $n$ 的相同顶点集，其中顶点的编号为 $1, 2, \dots, n$。

对于给定的 $k$，Minseok 从 $T_1$ 中选择 $k$ 条边，Martin 从 $T_2$ 中选择 $n - 1 - k$ 条边。他们选择的边的并集必须构成一棵树。如果可行，他们需要最小化所选边的总权重。

输入格式

第一行包含一个整数 $N$，表示两棵树的顶点数。

接下来的 $N - 1$ 行，给出第一棵树的描述。这 $N - 1$ 行中的每一行包含三个整数 $S_i, E_i, W_i$，表示有一条连接顶点 $S_i$ 和 $E_i$ 且权重为 $W_i$ 的边。

接下来的 $N - 1$ 行，以相同的格式给出第二棵树的描述。

输出格式

对于所有 $0 \le k \le n - 1$，输出最小总权重，如果不可能则输出 -1。

数据范围

• $2 \le N \le 250\,000$
• $1 \le S_i, E_i \le N, 1 \le W_i \le 10^9$ ($1 \le i \le N - 1$)

样例

输入样例 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

100
85
80
85
110

输入样例 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

48529
39568
31019
26748
25491
25661
29669
33975
42300