다리 건설

그라프 칸타리아 섬나라에는 $N$개의 섬이 $N - 1$개의 다리로 연결되어 있고, 이 다리들을 이용하면 어떤 두 섬 사이든 이동할 수 있다.

대통령 Vick T. Adgraf와 그녀의 남편 Rick T. Adgraf는 이 인프라 구축에 문제가 있다는 것을 깨달았다. 다리는 섬 사이를 빠르게 이동하기 위해서가 아니라 비용이 저렴해서 지어졌다. 지지율을 높이기 위해 Vick과 Rick은 왕국에 다리를 하나씩 더 짓고 싶어 한다. 두 사람은 새로 지을 다리에 대한 몇 가지 제안을 적어 두었고, 추가 다리가 특정 섬 쌍 사이의 거리를 어떻게 바꾸는지 비교하려고 한다.

당신의 임무는 왕국의 현재 모든 다리와 0개, 1개 또는 2개의 추가 다리 목록이 주어졌을 때, 추가 다리들을 지은 후 두 섬 사이의 최단 거리가 얼마가 되는지 답하는 프로그램을 작성하는 것이다.

첫째 줄에는 정수 $2 \le N \le 10^5$가 주어진다. 그다음 $N - 1$개의 줄이 주어지며, 각 줄은 현재 다리 하나를 나타낸다. $i$번째 줄에는 정수 $0 \le A[i] \not= B[i] < N$과 $1 \le L[i] \le 1000$이 주어진다. $A[i]$와 $B[i]$는 $i$번째 다리의 양 끝 섬이고, 이 다리의 길이는 $L[i]$이다.

다음 줄에는 정수 $0 \le E \le 2$가 주어지며, 이는 프로그램이 고려해야 할 추가 다리의 수이다. 그다음 $E$개의 줄에는 추가 다리 하나의 설명이 원래 다리와 같은 형식으로 주어진다. 추가 다리는 원래 다리나 다른 추가 다리와 겹치지 않는다.

다음 줄에는 $0 \le Q \le 10^5$가 주어지며, 이는 최단 거리를 구해야 할 섬 쌍의 수이다. 그다음 $Q$개의 줄이 주어진다. 이 중 $i$번째 줄에는 서로 다른 두 정수 $F[i]$와 $T[i]$가 주어진다.

$Q$개의 줄을 출력한다. $i$번째 줄에는 섬 $F[i]$와 $T[i]$ 사이의 최단 거리를 출력한다.