시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 1 1 1 100.000%

## 문제

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 weight of an 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 weights of the edges 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 on $a$. You are given $q$ queries, each of them is described with two integers, $u$ and $v$. For each query, you need to 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 of them should contain a single integer: the answer to the $i$-th query.

## 예제 입력 1

5 4
1 2 2
2 3 1
3 4 3
3 5 4
1 4
1 5
4 2
5 2


## 예제 출력 1

7
8
6
8