問題文

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

カズマくんは 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 と連結である。

辺を取り除くときには、取り除いた辺の重みの総和分のエネルギーを消費します。 カズマくんが達成できる最小の消費エネルギーを求めてください。

制約

• 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 は葉ではない
• 入力はすべて整数で与えられる

入力例 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 の葉 x と T_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