Minimum Road Construction Cost

You are given two trees \(T_1\) and \(T_2\), each with \(n\) nodes (numbered from 1 to \(n\)) and \(n-1\) weighted edges. The distance between two nodes \(i\) and \(j\) in tree \(T_k\) is defined as the sum of the weights along the unique simple path connecting them in \(T_k\), denoted as \(d_{T_k}(i,j)\), where \(k=1,2\).

A new road connecting nodes \(i\) and \(j\) can be constructed at a cost of \[ \text{cost}(i,j)=d_{T_1}(i,j)+d_{T_2}(i,j). \]

The task is to select a set of new roads such that all nodes are connected (i.e. the new roads form a spanning tree) and the total construction cost is minimized. Compute the minimum possible total cost.

Note: It is guaranteed that the input trees are connected and may have up to a small number of nodes so that an \(O(n^2)\) solution is acceptable.

inputFormat

The first line contains an integer \(n\) (\(2 \le n \le N\)), the number of nodes.

Then follow \(n-1\) lines for tree \(T_1\). Each of these lines contains three integers \(u\), \(v\), and \(w\) indicating an undirected edge between nodes \(u\) and \(v\) with weight \(w\).

Then follow another \(n-1\) lines for tree \(T_2\) in the same format.

It is guaranteed that 1 ≤ u, v ≤ n and all weights are positive integers.

outputFormat

Output a single integer, the minimum total cost to construct a set of new roads so that all nodes become connected.

sample

2
1 2 3
1 2 4

7