Wind of Change 2020

There is a tree $T_1$ with $N$ vertices. Each vertex of $T_1$ is numbered from 1 to $N$, and each edge has an integer weight (which may be negative). The maximum distance between two vertices of $T_1$ is called the diameter of the tree. The two vertices may be the same vertex.

Gu Jae-hyeon, a student who met this problem in a lab session, came up with the following approach. Root the tree at vertex 1. Then the distance between two vertices $x, y$ is

$depth_1(x) + depth_1(y) - depth_1(LCA_1(x, y)) - depth_1(LCA_1(x, y))$

Here $depth_1(x)$ is the distance from the root to vertex $x$ in $T_1$, and $LCA_1(x, y)$ is the lowest common ancestor of $x$ and $y$ in $T_1$. Gu uses a Sparse Table to find an LCA in $O(\log N)$. So by taking the maximum of this value over all $1 \le x, y \le N$, the problem can be solved in $O(N^2 \log N)$.

The first line contains the number of vertices $N$ of both trees ($1 \le N \le 400000$).

The next $N-1$ lines each contain three integers $u_i, v_i, w_i$. This means that tree $T_1$ has an edge of weight $w_i$ connecting vertices $u_i$ and $v_i$ ($1 \le u_i, v_i \le N$, $|w_i| \le 2^{31} - 1$).

The next $N-1$ lines each contain three integers $u_i, v_i, w_i$. This means that tree $T_2$ has an edge of weight $w_i$ connecting vertices $u_i$ and $v_i$ ($1 \le u_i, v_i \le N$, $|w_i| \le 2^{31} - 1$).

Print one integer, the answer to the problem.