Wind of Change 2020

$N$ 개의 정점으로 이루어진 트리 $T\_1$ 가 있다. $T\_1$의 각 정점에는 1부터 $N$까지의 번호가 부여되어 있고, 각 간선에는 정수 가중치 (음수일 수 있음) 가 부여되어 있다. $T\_1$ 에서 두 정점 간의 거리의 최댓값을 트리의 지름이라고 한다. 이 때 두 정점은 같은 정점일 수 있다.

실습에서 이 문제를 접한 구재현 학생은 다음과 같은 풀이를 생각했다. 트리의 루트를 1번 정점으로 두었을 때, 두 정점 $x, y$ 간의 거리는 

$depth\_1(x) + depth\_1(y) - depth\_1(LCA\_1(x, y)) - depth\_1(LCA\_1(x, y))$

이다. 이 때 $depth\_1(x)$ 는 $T\_1$ 에서 루트와 정점 $x$ 의 거리이고, $LCA\_1(x, y)$ 는 $T\_1$ 에서 두 정점 $x, y$ 의 LCA이다. 구재현 학생은 Sparse Table을 사용해서 LCA를 $O(\log N)$ 에 구할 수 있다. 고로, 모든 $1 \le x, y \le N$ 에 대해서 해당 값의 최댓값을 구하면 $O(N^2 \log N)$ 에 문제를 해결할 수 있다. 

구재현 학생은, 이 알고리즘을 구현하고 시간 초과를 받았다. 자존심이 상한 구재현 학생은, 위 문제를 조금 바꿔서 코치들에게 도전하기로 하였다. $T\_2$를 $T\_1$ 과 동일한 형식으로 주어지는 트리라고 하고, $depth\_2(x), LCA\_2(x, y)$ 역시 비슷하게 정의 할 때, 다음 값을 계산하자:

$\max\_{1 \le x, y \le N} (depth\_1(x) + depth\_1(y) - depth\_1(LCA\_1(x, y)) - depth\_2(LCA\_2(x, y)))$

훌륭한 코치인 여러분 역시 자존심이 강하다. 이 문제를 풀어서, 하라는 공부는 안하고 이상한 자료구조 문제나 만드는 구재현 학생의 콧대를 꺾어주자.

첫 번째 줄에 두 트리의 정점 수 $N$ ($1 \le N \le 400\\,000$) 이 주어진다.

이후 $N-1$ 개의 줄에 세 정수 $u\_i, v\_i, w\_i$ 가 주어진다. $T\_1$ 에 두 정점 $u\_i, v\_i$ 를 잇는 가중치 $w\_i$ 의 간선이 있음을 뜻한다. ($1 \le u\_i, v\_i \le N, |w\_i| \le 2^{31} - 1$)

이후 $N-1$ 개의 줄에 세 정수 $u\_i, v\_i, w\_i$ 가 주어진다. $T\_2$ 에 두 정점 $u\_i, v\_i$ 를 잇는 가중치 $w\_i$ 의 간선이 있음을 뜻한다. ($1 \le u\_i, v\_i \le N, |w\_i| \le 2^{31} - 1$)

하나의 정수로 문제의 정답을 출력하라.