J - Link-cut tworee /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

あるところに、木こりのカズマくんがいました。

カズマくんは 2 つの N 頂点の根付き木 T_1, T_2 を持っています。 T_1, T_2 の根はそれぞれ頂点 1 であり、T_1, T_2 の葉の数は同じです。 また、どちらの木においても頂点 1 は葉ではありません。

T_1i 番目の辺は頂点 a_ib_i を結び、w_i の重みを持つ無向辺です。 同様に T_2i 番目の辺は頂点 c_id_i を結び、v_i の重みを持つ無向辺です。

カズマくんは T_1, T_2 を組み合わせて、新しい2つの木を以下の手順で作ることにしました。

  • T_1T_2 の葉を一対一対応させ、対応させた葉同士を縮約し、1 つのグラフを作る。
  • その後、作ったグラフからいくつか辺を取り除いて、以下の3つの条件を満たすようにする。
    • T_1 の頂点 1T_2 の頂点 1 は非連結である。
    • T_1 の頂点 1 が属する連結成分が木となる。T_2 の頂点 1 についても同様である。
    • 任意の頂点は T_1 の頂点 1 または T_2 の頂点 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 は葉ではない
  • 入力はすべて整数で与えられる

入力

入力は以下の形式で標準入力から与えられる。

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}

出力

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


入力例 1

5
1 2 1
1 5 3
2 3 4
2 4 6
1 2 8
1 3 7
2 4 2
2 5 5

出力例 1

6

T_1 の葉 xT_2 の葉 y で縮約」を「(x, y) で縮約」と書くことにします。 カズマくんはまず (3, 3), (4, 4), (5, 5) で縮約し、その後上記の図で点線となっている辺を取り除きます。 このとき消費エネルギーは 6 となり、これが最小です。


入力例 2

6
1 2 1000000000
1 3 1000000000
1 4 1000000000
1 5 1000000000
1 6 1000000000
1 2 1000000000
1 3 1000000000
1 4 1000000000
1 5 1000000000
1 6 1000000000

出力例 2

5000000000

入力例 3

7
1 2 8613
3 6 91
2 5 20238
3 7 5018
1 3 10453
2 4 7580
3 7 123
2 5 24095
1 2 6957
2 4 13166
1 3 72
2 6 2444

出力例 3

7625