AT_kupc2019_j Link-cut tworee

给定两棵 $N$ 个节点的以 $1$ 为根的树，边有边权，保证两棵树的叶子节点个数相同。你要将两棵树上的叶子节点两两匹配，可以抽象为在一棵树中选一个叶子 $u$，另一棵树中选一个叶子 $v$，连边 $(u,v,inf)$。这样两棵树形成了一张图。 接着，你需要删掉一些边，使得图变成两棵树，并满足原先的两个 $1$ 号节点在不同的树中。 求删去的边的最小边权和。

第一行读入一个整数 $N$，表示树的结点个数。 接下来 $N-1$ 行，每行三个整数 $u,v,w$，表示第一棵树上 $u,v$ 之间有一条边权为 $w$ 的边。 接下来 $N-1$ 行，每行三个整数 $u,v,w$，表示第二棵树上 $u,v$ 之间有一条边权为 $w$ 的边。

一行一个整数，表示最小边权和。

### 制約 - $ 3\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ a_i,\ b_i,\ c_i,\ d_i\ \leq\ N $ - $ 1\ \leq\ w_i,\ v_i\ \leq\ 10^9 $ - $ 2 $ つのグラフはどちらも木である - $ 2 $ つのグラフの葉の数は等しい - $ 2 $ つのグラフのそれぞれにおいて、頂点 $ 1 $ は葉ではない - 入力はすべて整数で与えられる ### Sample Explanation 1 !\[\](https://img.atcoder.jp/kupc2019/e05f02db9330d95b2c5093abe710c8cb.png) 「$ T_1 $ の葉 $ x $ と $ T_2 $ の葉 $ y $ で縮約」を「$ (x,\ y) $ で縮約」と書くことにします。 カズマくんはまず $ (3,\ 3) $, $ (4,\ 4) $, $ (5,\ 5) $ で縮約し、その後上記の図で点線となっている辺を取り除きます。 このとき消費エネルギーは $ 6 $ となり、これが最小です。