27730번 - 견우와 직녀 스페셜 저지

문제

견우는 정점의 개수가 $N$인 무향 가중치 트리 $E$에 살고 있고, 직녀는 정점의 개수가 $M$인 무향 가중치 트리 $W$에 살고 있다.

두 사람은 각자 다른 트리에 살고 있으므로 만날 수 없다... 슬픔에 빠진 두 사람을 위해 옥황상제는 매년 7월 7일이 되면 오작교를 이어 두 사람이 만날 수 있게 해주려고 한다.

오작교는 길이가 1ドル$인 간선이며 옥황상제는 두 사람이 만나기 쉽도록 $E$의 모든 정점과 $W$의 모든 정점 사이의 거리의 합이 최소가 되도록 이어주려고 한다.

견우와 직녀를 위해 7월 7일이 되면 어떤 정점에서 오작교가 이어지는지 알려주도록 하자!

입력

첫째 줄에 $E$의 정점 개수 $N(1 \leq N \leq 100,000円)$이 주어진다.

다음 $N-1$개의 줄에 걸쳐 $E$의 간선이 a b c$(1 \leq a, b \leq N; 1 \leq c \leq 10^4)$와 같은 형식으로 주어진다. 이는 $E$의 $a$번 정점과 $b$번 정점 사이의 거리가 $c$라는 것을 뜻한다.

다음 줄에 $W$의 정점 개수 $M(1 \leq M \leq 100,000円)$이 주어진다.

다음 $M-1$개의 줄에 걸쳐 $W$의 간선이 a b c$(1 \leq a, b \leq M; 1 \leq c \leq 10^4)$와 같은 형식으로 주어진다. 이는 $W$의 $a$번 정점과 $b$번 정점 사이의 거리가 $c$라는 것을 뜻한다.

주어지는 입력은 모두 정수다.

출력

첫째 줄에 오작교가 이어지게 되는 $E$의 정점 번호와 $W$의 정점 번호를 공백을 사이에 두고 차례대로 출력한다. 가능한 경우가 여러 가지라면 그 중 아무거나 출력한다.

둘째 줄에 오작교가 이어진 후 $E$의 모든 정점과 $W$의 모든 정점 사이의 거리의 합을 출력한다.

제한

힌트

$E$의 모든 정점과 $W$의 모든 정점 사이의 거리의 합을 수학적으로 정의하면 다음과 같다.

\[ \sum_{u \in E} \sum_{v \in W} dist(u, v) \]