Problem Description

There was a lumberjack named Kazuma.

Kazuma has two rooted trees with $ N $ vertices each, $ T_1 $ and $ T_2 $. The roots of $ T_1 $ and $ T_2 $ are vertex $ 1 $, and both trees have the same number of leaves. Also, in both trees, vertex $ 1 $ is not a leaf.

The $ i $ -th edge of $ T_1 $ connects vertices $ a_i $ and $ b_i $ with an undirected edge of weight $ w_i $. Similarly, the $ i $ -th edge of $ T_2 $ connects vertices $ c_i $ and $ d_i $ with an undirected edge of weight $ v_i $.

Kazuma decided to combine $ T_1 $ and $ T_2 $ to create two new trees following these steps:

• Pair the leaves of $ T_1 $ and $ T_2 $ one-to-one, and contract the paired leaves to create a single graph.
• Then, remove some edges from the created graph to satisfy the following three conditions:
• Vertex $ 1 $ of $ T_1 $ and vertex $ 1 $ of $ T_2 $ are disconnected.
• The connected component containing vertex $ 1 $ of $ T_1 $ forms a tree. The same applies to vertex $ 1 $ of $ T_2 $.
• Any vertex is connected to either vertex $ 1 $ of $ T_1 $ or vertex $ 1 $ of $ T_2 $.

When removing edges, the energy consumed is the total weight of the removed edges. Find the minimum energy Kazuma can achieve.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output the minimum energy that can be achieved.

Sample Input and Output

Sample Input #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

Sample Output #1

6

Sample Input #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

Sample Output #2

5000000000

Sample Input #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

Sample Output #3

7625

Notes/Hints

Constraints

• $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$
• Both graphs are trees.
• The number of leaves in both graphs is equal.
• In each graph, vertex $ 1 $ is not a leaf.
• All inputs are integers.

Sample Explanation 1

Let "contract $ T_1 $ 's leaf $ x $ and $ T_2 $ 's leaf $ y $" be written as "contract at $ (x, y) $". Kazuma first contracts at $ (3, 3) $, $ (4, 4) $, $ (5, 5) $, and then removes the edges shown as dotted lines in the figure above. The energy consumed at this time is $ 6 $, which is the minimum.

见题面 Input 部分

见题面 Output 部分