접두사 최댓값

트리는 임의의 두 정점이 정확히 하나의 경로로 연결된 무방향 그래프입니다. 정점이 $n$개인 가중치 트리가 주어집니다. $w(i, j)$는 정점 $i$와 $j$를 잇는 간선의 가중치입니다. 정점 $u$에서 정점 $v$로 가는 단순 경로 $P = (u, s_1, \dots, s_{t-1}, v)$를 생각합니다. 경로 $P$의 간선 가중치 수열을 $a = (a_1, a_2, \dots, a_t)$라 하면, $a_1 = w(u, s_1)$, $a_2 = w(s_1, s_2)$, $\dots$, $a_t = w(s_{t-1}, v)$입니다.

$f(u, v) = \sum_{i=1}^{t} \max_{j=1 \dots i}\{a_j\}$는 $a$의 접두사 최댓값의 합입니다. $q$개의 질의가 주어지며, 각 질의는 두 정수 $u$와 $v$로 표현됩니다. 각 질의에 대해 $f(u, v)$를 구하세요.

첫 줄에 트리의 정점 수 $n$과 질의 수 $q$가 공백으로 구분되어 주어집니다 ($1 \le n \le 2 \cdot 10^5$, $1 \le q \le 10^6$).

이어지는 $n - 1$개의 줄에는 각각 세 정수 $a_i$, $b_i$, $c_i$가 주어집니다 ($1 \le a_i, b_i \le n$, $a_i \ne b_i$, $1 \le c_i \le 10^9$). 이는 $i$번째 간선이 잇는 두 정점과 그 가중치입니다. 주어지는 간선들은 트리를 이룹니다.

이어지는 $q$개의 줄에는 각각 두 정수 $u_i$와 $v_i$ ($1 \le u_i, v_i \le n$)가 주어집니다. 이는 $i$번째 질의입니다.

$q$개의 줄을 출력합니다. $i$번째 줄에는 $i$번째 질의의 답을 정수 하나로 출력합니다.