AT_kupc2019_j Link-cut tworee

[problemUrl]: https://atcoder.jp/contests/kupc2019/tasks/kupc2019_j あるところに、木こりのカズマくんがいました。 カズマくんは $ 2 $ つの $ N $ 頂点の根付き木 $ T_1,\ T_2 $ を持っています。 $ T_1,\ T_2 $ の根はそれぞれ頂点 $ 1 $ であり、$ T_1,\ T_2 $ の葉の数は同じです。 また、どちらの木においても頂点 $ 1 $ は葉ではありません。 $ T_1 $ の $ i $ 番目の辺は頂点 $ a_i $ と $ b_i $ を結び、$ w_i $ の重みを持つ無向辺です。 同様に $ T_2 $ の $ i $ 番目の辺は頂点 $ c_i $ と $ d_i $ を結び、$ v_i $ の重みを持つ無向辺です。 カズマくんは $ T_1,\ T_2 $ を組み合わせて、新しい2つの木を以下の手順で作ることにしました。 - $ T_1 $ と $ T_2 $ の葉を一対一対応させ、対応させた葉同士を縮約し、$ 1 $ つのグラフを作る。 - その後、作ったグラフからいくつか辺を取り除いて、以下の3つの条件を満たすようにする。 - $ T_1 $ の頂点 $ 1 $ と $ T_2 $ の頂点 $ 1 $ は非連結である。 - $ T_1 $ の頂点 $ 1 $ が属する連結成分が木となる。$ T_2 $ の頂点 $ 1 $ についても同様である。 - 任意の頂点は $ T_1 $ の頂点 $ 1 $ または $ T_2 $ の頂点 $ 1 $ と連結である。 辺を取り除くときには、取り除いた辺の重みの総和分のエネルギーを消費します。 カズマくんが達成できる最小の消費エネルギーを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ b_1 $ $ w_1 $ $ a_2 $ $ b_2 $ $ w_2 $ $ : $ $ a_{N\ -\ 1} $ $ b_{N\ -\ 1} $ $ w_{N\ -\ 1} $ $ c_1 $ $ d_1 $ $ v_1 $ $ c_2 $ $ d_2 $ $ v_2 $ $ : $ $ c_{N\ -\ 1} $ $ d_{N\ -\ 1} $ $ v_{N\ -\ 1} $

達成できる最小の消費エネルギーを出力せよ。

### 制約 - $ 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 $ となり、これが最小です。