Background

感谢sszcdjr对此题的贡献

模仿一下Conflict题面风格

Description

当前的 世界 为由 \(n\) 个节点组成的一个无向连通图, 一共有 \(n-1\) 条边, 每条边有一个权值称为 长度.

每次往当前的 世界 中加入一次 行军 , 行军 为一条路径, 两次 行军 之间有一个 隔阂 .

• 若两条 行军 的路径重合, 则它们的 隔阂 值是重合部分 长度 的和的相反数.
• 若不重合,则一个信使会选择一条路径称为 传信路 满足两个端点分别在一个 行军 的路径上, 隔阂程度为 传信路 的长度的最小值.

每次加入 行军 前,你需要求出这次 行军 和之前的所有 行军 的 隔阂值的和.

Format

Input

第一行两个整数n,q,n为节点数,q为 行军 个数

接下来 \(n-1\) 行每行两个整数 \(u\),\(v\),\(w\) 描述一条边的两端和 长度 .

接下来 \(q\) 行每行两个整数 \(u\),\(v\)描述一次 行军 的路径.

Output

q行,每行一个整数表示所求的 隔阂 值的总和.

Sample 1

Input

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

Output

0
1

Limitation

1s, 1024KiB for each test case.

所有输入都是正整数.

子任务	占比	\(n\le\)	\(q\le\)	\(w_i\le\)
Subtask1	\( 20\% \)	\(100\)	\(100\)	\(10\)
Subtask2	\( 20\% \)	\(1000\)	\(1000\)	\(10^9\)
Subtask3	\( 20\% \)	\(10^5\)	\(10^5\)	\(1\)
Subtask3	\( 40\% \)	\(10^5\)	\(10^5\)	\(10^9\)

Hint