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

노트