배송

샘은 트럭 운전사로 일하며 여러 창고 사이를 오가며 물품을 배송한다. 창고는 모두 N개이다. 일부 창고는 도로로 연결되어 있으며, 임의의 두 창고 사이를 잇는 길은 정확히 하나뿐이다. 그 길은 중간에 다른 창고를 여러 개 지날 수도 있다.

샘은 배터리로 움직이는 여러 트럭을 사용한다. 각 트럭에는 접이식 태양광 패널이 있어서, 트럭이 멈춰 있을 때만 배터리를 충전할 수 있다. 한 창고에서 다른 창고로 이동하는 동안 샘은 원하는 지점에서 멈춰 배터리를 충전할 수 있다. 배터리가 방전되면 트럭은 움직일 수 없다. 또한 샘은 보안상의 이유로 지나가는 창고마다 반드시 멈춰야 한다. 창고에 멈출 때에도 배터리를 충전할 수 있다.

샘은 자주 멈추는 것을 싫어하므로, 각 경로마다 필요한 최소 정차 횟수를 구해 달라고 부탁했다. 이 횟수에는 충전을 위한 정차와 창고에서의 정차가 모두 포함되며, 출발 창고와 도착 창고(짐을 싣고 내리는 곳)에서의 정차도 포함된다.

첫째 줄에 창고의 수 N과 샘이 이동하는 경로의 수 Q가 주어진다. 여기서 $1 \le N, Q \le 100{,}000$이다. 이어지는 N-1개의 줄에는 창고 사이의 도로가 주어진다. 각 줄에는 세 정수 U, V, D가 있다. U와 V는 창고의 번호이며 $1 \le U, V \le N$이다. D는 창고 U와 V 사이 도로의 길이(킬로미터)이며 $1 \le D \le 20{,}000$이다. 이어지는 Q개의 줄에는 샘의 경로가 주어진다. 각 줄에는 세 정수 S, F, T가 있다. S와 F는 경로의 출발 창고와 도착 창고의 번호이며 $1 \le S, F \le N$이고 $S \neq F$이다. T는 이 경로에서 사용하는 트럭의 배터리 용량으로, 완전히 충전했을 때 트럭이 갈 수 있는 거리(킬로미터)이다. 여기서 $1 \le T \le 20{,}000$이다.

Q개의 경로 각각에 대해, 그 경로에서 필요한 최소 정차 횟수를 한 줄에 출력한다.