24520번 - Meet In The Middle

신촌 왕국에는 $1$번부터 $N$번까지 $N$개의 마을이 있고 $N-1$개의 도로가 서로 다른 두 마을을 연결하고 있다. 모든 마을은 도로를 통해 다른 마을로 갈 수 있고, 이때 마을 내에서의 이동 거리는 무시할 수 있다.

현재 신촌 왕국은 "대칭병"의 대유행으로 혼란을 겪고 있다. 대칭병은 어떤 것이든 대칭을 이루지 않으면 심신이 불편해져 일상생활을 할 수 없게 만드는 병이다. 대칭병의 여파는 엄청났는데 심지어 사람과 사람 간의 만남조차 어렵게 됐다. 신촌 왕국의 두 사람이 만나는 상황을 생각해보자. 약속 장소가 둘 중 한 사람의 마을에 더 가깝다면 아주 불편해진다. 따라서 두 사람이 사는 각 마을까지의 거리가 정확히 같은 곳을 약속 장소로 정해야 할 것이다. 즉, Meet in the middle. 가운데에서 만나야 한다!

신촌 왕국 도로 정보와 만나려는 두 사람의 마을이 주어졌을 때, 약속 장소로 적절한 위치를 구해보자.

첫 번째 줄에 마을의 수 $N$, 약속의 수 $K$가 주어진다. $(1 \le N, K \le 100\,000)$

이어지는 줄부터 $N-1$개의 줄에 도로 정보를 나타내는 세 정수 $u$, $v$, $w$가 주어진다. $u$번 마을과 $v$번 마을 사이에 길이 $w$의 도로가 있다는 뜻이다. $(1 \le u, v \le N$, $u \neq v$, $1 \le w \le 10^9)$

이어지는 줄부터 $K$개의 줄에 만나려는 두 사람의 마을 번호 $u$, $v$가 주어진다. $(1 \le u, v \le N)$

$K$개의 줄에 두 사람의 만날 수 있는 마을의 번호를 출력한다. 그러한 마을이 없다면 -1을 출력한다. 가능한 답이 여러 가지라면, 두 사람이 사는 각 마을까지 거리의 합이 짧은 것을 출력한다.