Intellectual Prefix Maxima

A tree is an undirected graph in which any two vertices are connected by exactly one path. You are given a weighted tree with $n$ vertices, where $w(i, j)$ is the weight of the edge between vertices $i$ and $j$. Consider a simple path $P = (u, s_1, \dots, s_{t-1}, v)$ from vertex $u$ to vertex $v$. Denote the sequence of edge weights on path $P$ by $a = (a_1, a_2, \dots, a_t)$, where $a_1 = w(u, s_1)$, $a_2 = w(s_1, s_2)$, $\dots$, $a_t = w(s_{t-1}, v)$.

Let $f(u, v) = \sum_{i=1}^{t} \max_{j=1 \dots i}\{a_j\}$ be the sum of prefix maxima of $a$. You are given $q$ queries, each described by two integers $u$ and $v$. For each query, compute $f(u, v)$.

The first line contains two integers $n$ and $q$ ($1 \le n \le 2 \cdot 10^5$, $1 \le q \le 10^6$), separated by a single space: the number of vertices in the tree and the number of queries.

Each of the next $n - 1$ lines contains three integers $a_i$, $b_i$, and $c_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$, $1 \le c_i \le 10^9$): the vertices connected by the $i$-th edge and its weight. It is guaranteed that the given edges form a tree.

Each of the next $q$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$): the $i$-th query.

Print $q$ lines. The $i$-th line contains a single integer: the answer to the $i$-th query.