모임과 쿼리

가중치 있는 트리 구조의 마을에서 $1$번부터 $N$번까지 $N$명의 사람들이 살고 있다. $i$번 사람은 $i$번 정점에 살고 있다.

사람들은 모임을 $Q$번 갖는데, $k$번째 모임에서는 $1$ 이상 $N$ 이하의 원하는 정수 $x\_k$를 골라 번호가 $\ell\_k$ 이상 $r\_k$ 이하인 사람들이 참여한다.

$k$번째 모임에 걸리는 시간 $t\_k$는 모임에 참여하는 각 사람과 $x\_k$까지의 거리 중 최댓값이다.

$t\_k$가 최소가 되도록 $x\_k$를 고를 때, 각 모임에 걸리는 시간 $t\_k$를 계산해 보자.

첫째 줄에 사람들의 수 $N$과 모임의 수 $Q$가 공백으로 구분되어 주어진다. ($1 \le N, Q \le 100\\,000$)

다음 $N-1$개 줄 중 $i$번째 줄에는 트리의 간선 정보를 나타내는 정수 $a\_i$, $b\_i$, $c\_i$가 공백으로 구분되어 주어진다. 이는 $a\_i$번 정점과 $b\_i$번 정점을 잇는 가중치가 $c\_i$인 간선이 있다는 뜻이다. ($1 \le a\_i, b\_i \le N$, $1 \le c\_i \le 10^9$, $a\_i \ne b\_i$)

다음 $Q$개 줄 중 $k$번째 줄에는 $k$번째 모임에 참여하는 사람들의 번호 범위를 나타내는 정수 $\ell\_k$, $r\_k$가 공백으로 구분되어 주어진다. ($1 \le \ell\_k \le r\_k \le N$)

각 모임마다 모임에 걸리는 시간 $t\_k$를 한 줄에 출력한다.