34655번 - Halcyon 다국어

Minseok and Martin have two weighted trees $T_1, T_2$. They share the same vertex set of size $n$, where we index each vertex with integers from $1, 2, \ldots, n$.

For a given $k$, Minseok selects $k$ edges from $T_1$, and Martin selects $n-1-k$ edges from $T_2$. The union of their selected edges should form a tree. If this is possible, they should minimize the total weight of selected edges.

In the first line, a single integer $N$ denoting the number of vertices in both trees is given.

In the next $N-1$ lines, description of the first tree is given. Each of the $N-1$ lines contains three integers $S_i, E_i, W_i$, which indicates there is an edge connecting two vertices $S_i, E_i$ with weight $W_i$.

In the next $N-1$ lines, description of the second tree is given in the same format.

For all $0 \le k \le n - 1$, print the minimum total weight, or print -1 if it is impossible.

• $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$)