TOLLS

Ivo 나라에는 $N$개의 도시가 있고, 이 도시들은 $N-1$개의 양방향 고속도로로 연결되어 있다. 고속도로를 따라 어떤 도시에서든 다른 모든 도시로 갈 수 있다. 고속도로 $i$는 서로 다른 두 도시 $u_i$, $v_i$를 잇고, 통행료 $w_i$를 받는다 ($1 \leq i \leq N-1$).

여행은 서로 다른 두 도시 $u$, $v$ 사이의 단순 경로(같은 도시를 두 번 지나지 않는 경로)다. 여행의 비용은 경로 위 통행료의 합이 아니다. 경로에 있는 고속도로 통행료 중 가장 큰 값 하나만 지불한다.

정부가 $Q$개의 질문을 한다. $j$번째 질문($1 \leq j \leq Q$)은 비용이 $[l_j, r_j]$ 구간에 있는 모든 여행의 비용 합을 구하는 것이다. 첫 번째 질문은 서로 다른 모든 도시 쌍을 대상으로 하므로 $l_1=1$, $r_1=\max_{1 \leq i \leq N-1}\{w_i\}$이다.

첫 줄에 도시의 수 $N$과 질문의 수 $Q$가 양의 정수로 주어진다. 이어서 $N-1$개의 줄에 도시 $u_i$, $v_i$를 잇고 통행료가 $w_i$인 고속도로를 나타내는 양의 정수 $u_i$, $v_i$, $w_i$가 주어진다. 마지막 $Q$개의 줄에는 질문을 나타내는 양의 정수 $l_j$, $r_j$가 주어진다.

각 질문에 대해, 입력 순서대로 비용이 $[l_j, r_j]$ 구간에 있는 모든 여행의 비용 합을 한 줄에 하나씩 출력한다.

• $1 \leq N, Q \leq 10^5$
• $1 \leq u_i, v_i \leq N-1$
• $1 \leq w_i \leq 10^9$
• $1 \leq l_j \leq r_j \leq 10^9$

아래 그림은 도시와 고속도로를 나타낸다.

• 비용이 $1$인 여행은 $3$개다: $1-2$, $1-4$, $2-4$.
• 비용이 $2$인 여행은 $4$개다: $1-5$, $2-5$, $3-6$, $4-5$.
• 비용이 $3$인 여행은 $8$개다: $1-3$, $1-6$, $2-3$, $2-6$, $3-4$, $3-5$, $4-6$, $5-6$.
• 비용이 $4$인 여행은 $6$개다: $1-7$, $2-7$, $3-7$, $4-7$, $5-7$, $6-7$.
• 비용이 $5$인 여행은 $0$개다.

첫 번째 질문의 답은 $3 \times 1+4 \times 2+8 \times 3+6 \times 4=59$이다. 두 번째 질문의 답은 $4 \times 2+8 \times 3=32$이다. 세 번째 질문의 답은 $4 \times 2+8 \times 3+6 \times 4=56$이다. 네 번째 질문의 답은 $3 \times 1+4 \times 2+8 \times 3=35$이다. 다섯 번째 질문의 답은 $4 \times 2+8 \times 3+6 \times 4+0 \times 5=56$이다.