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$의 최소 공통 조상이다. 구재현 학생은 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 400000$)이 주어진다.

이후 $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$)

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