Meet In The Middle

The kingdom of Sinchon has $N$ villages numbered $1$ through $N$, connected by $N-1$ roads, each joining two distinct villages. Every village can be reached from every other village by roads, and travel within a village takes no distance.

Sinchon is now in turmoil from a pandemic of "symmetry sickness." A person with symmetry sickness feels uneasy in body and mind unless everything is symmetric, to the point of being unable to carry on daily life. The aftermath is so severe that even meetings between people have become difficult. Consider two people in Sinchon who want to meet. If the meeting place is closer to one person's village than the other's, they become very uncomfortable. So the meeting place must be chosen at a spot whose distance to each person's village is exactly the same. In other words, Meet in the middle. They must meet in the middle!

Given the road information of Sinchon and the villages of the two people who want to meet, find a suitable location for the meeting place.

The first line gives the number of villages $N$ and the number of meetings $K$. $(1 \le N, K \le 100\,000)$

The next $N-1$ lines give three integers $u$, $v$, $w$ describing a road. This means there is a road of length $w$ between village $u$ and village $v$. $(1 \le u, v \le N$, $u \neq v$, $1 \le w \le 10^9)$

The next $K$ lines give the village numbers $u$, $v$ of the two people who want to meet. $(1 \le u, v \le N)$

For each of the $K$ lines, print the number of a village where the two people can meet. If no such village exists, print -1. If there are several possible answers, print the one with the smallest sum of distances to the two people's villages.