temporaryDO is a mediocre OIer. In April, during the provincial team selection contest, he encountered the problem "Link-Cut Tree," where the partial credit for $k=0$ required finding the longest chain in a tree $T$. Poor temporaryDO did not know how to solve this problem and could not come up with any ideas while scratching his head in the exam hall.

At this moment, the kind Banban appeared in the air, emitting a brilliant yet gentle light that rippled across the exam hall. "The problem is not difficult," Banban said. The magnetic voice filled temporaryDO with strength. He decided to write a partial credit program with $O(n^2 \log n)$ complexity by enumerating all pairs of points to calculate the distance for $k=0$! Thus, temporaryDO chose $1$ as the root, built a heavy-light decomposition structure to find the LCA, and wrote a nested for loop to enumerate all pairs of points.

However, the clumsy temporaryDO accidentally declared an array that was too small, causing an out-of-bounds access into a mysterious memory region. As it happened, that memory region stored another tree $T'$. Consequently, the program did not crash, but when he calculated the distance between $x$ and $y$, it computed:

$$\text{depth}(x) + \text{depth}(y) - (\text{depth}(\text{LCA}(x, y)) + \text{depth}'(\text{LCA}'(x, y)))$$

Finally, the program outputs the maximum "distance" as defined above for all pairs of points $i, j$ ($i \le j$).

temporaryDO's program received a score of zero during evaluation. But he was not convinced; he decided to spend several days running his program. Please help poor temporaryDO find the output of his program based on $T$ and $T'$.

Input

The first line contains an integer $n$, representing the number of nodes in the trees.

The next $n-1$ lines each contain three integers $x, y, v$, representing an edge in $T$ between $x$ and $y$ with length $v$.

The next $n-1$ lines each contain three integers $x, y, v$, representing an edge in $T'$ between $x$ and $y$ with length $v$.

Output

Output a single integer representing the output of temporaryDO's program.

Examples

Input 1

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

Output 1

5

Note 1

The distance for the pair $(3, 4)$ is calculated as $3 + 0 - (0 + (-2)) = 5$.

Input 2

(See the files wronganswer/wronganswer2.in and wronganswer/wronganswer2.ans in the contestant directory)

Subtasks

For all data, $n \le 366,666$, $|v| \le 2,017,011,328$.

Note

$\text{depth}(p)$ and $\text{depth}'(p)$ represent the distance from node $1$ to node $p$ in trees $T$ and $T'$ respectively. Here, distance is defined as the sum of the weights of the edges on the path, with $\text{depth}(1) = 0$.

$\text{LCA}(x, y)$ and $\text{LCA}'(x, y)$ represent the lowest common ancestor of nodes $x$ and $y$ in trees $T$ and $T'$ respectively, which is the node on the shortest path between $x$ and $y$ that is closest to the root.