Byteland 有 $n$ 座城市，编号从 $1$ 到 $n$。城市之间由 $n-1$ 条双向道路和 $n-1$ 条双向铁路连接。对于任意两座城市，仅通过道路总是可以互相到达，仅通过铁路也是如此。

Alice 和 Bob 正在 Byteland 计划 $q$ 次长途旅行。在每次旅行中，Alice 从第 $a$ 座城市出发，仅通过道路访问其他一些城市；而 Bob 从第 $b$ 座城市出发，仅通过铁路访问其他一些城市。他们最终都会到达同一个目的地城市，且过程中不会访问任何城市超过一次。你需要找到在所有可能的目的地城市选择中，他们旅行路线的总长度之和的最大值。

输入格式

第一行包含两个整数 $n$ ($2 \le n \le 10^5$) 和 $q$ ($1 \le q \le 5 \times 10^5$)，分别表示 Byteland 的城市数量和旅行计划的数量。

接下来的 $n-1$ 行，每行包含三个整数 $u, v$ ($1 \le u, v \le n$) 和 $w$ ($1 \le w \le 10^9$)，表示连接第 $u$ 座城市和第 $v$ 座城市的一条长度为 $w$ 的道路。

接下来的 $n-1$ 行，每行包含三个整数 $u, v$ ($1 \le u, v \le n$) 和 $w$ ($1 \le w \le 10^9$)，表示连接第 $u$ 座城市和第 $v$ 座城市的一条长度为 $w$ 的铁路。

接下来的 $q$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \le a, b \le n$)，表示一次旅行，其中 Alice 从第 $a$ 座城市出发，Bob 从第 $b$ 座城市出发。

输出格式

输出 $q$ 行，每行包含一个整数，表示在所有可能的目的地城市选择中，Alice 和 Bob 旅行路线的总长度之和的最大值。

样例

输入 1

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

输出 1

6
4
5
3