개미

하둘우드 숲에는 1번부터 $n$번까지 번호가 붙은 개미집 $n$개가 있다. 개미집들은 양방향 터널로 연결되어 있고, 임의의 두 개미집을 잇는 단순 경로는 정확히 하나뿐이다.

봄이 되자 여왕개미가 개미집 구조의 연간 순환을 발표했다. 이 순환에는 일꾼 개미 $m$마리가 참여한다. $i$번째 개미는 $t_i$ 시각에 개미집 $a_i$를 떠나 최단 경로로 개미집 $b_i$까지 가야 한다. 모든 개미는 같은 속도로 움직이며, 목적지에 도착하기 전에는 멈추지 않는다.

여왕은 많은 개미가 한 지점에 모이면 반란이 일어날 수 있다고 의심한다. 각 일꾼 개미에 대해, 그 개미가 이동 중 한 지점(터널 내부 또는 개미집)에서 동시에 만나는 다른 이동 중 개미 수의 최댓값을 구하라. 만남은 이동 중에만 일어난다. $i$번째 개미가 시각 $t_i'$에 도착한다면, 개미 $i$와 $j$는 $t \in [t_i, t_i'] \cap [t_j, t_j']$인 시각에만 만날 수 있다.

첫 줄에 개미집 수 $n$과 일꾼 개미 수 $m$이 주어진다 ($1 \le n, m \le 100\,000$).

다음 $n - 1$개 줄에는 세 정수 $u_i$, $v_i$, $d_i$가 주어진다 ($1 \le u_i, v_i \le n$, $u_i \ne v_i$, $1 \le d_i \le 10^9$). 이는 개미집 $u_i$와 $v_i$가 양방향 터널로 연결되어 있고, 일꾼 개미가 이 터널을 지나는 데 $d_i$의 시간이 걸린다는 뜻이다.

마지막 $m$개 줄에는 일꾼 개미를 나타내는 세 정수 $a_i$, $b_i$, $t_i$가 주어진다 ($1 \le a_i, b_i \le n$, $a_i \ne b_i$, $1 \le t_i \le 10^9$).

$m$개 줄을 출력한다. $k$번째 줄에는 개미 $k$가 같은 시각에 만나는 이동 중 다른 개미 수(개미 $k$ 제외)의 최댓값을 출력한다.