在泰姆瑞尔大陆帝国的一个省份天际省，两个阵营之间爆发了内战。由乌弗里克·风暴斗篷领导的风暴斗篷由天际省土生土长的诺德人组成。他们的目标是建立一个不受帝国干涉的独立天际。由图留斯将军领导的帝国军团是帝国的军队，他们反对风暴斗篷，并试图重新统一和安抚该省。

乌弗里克·风暴斗篷当前的目标是进攻由图留斯将军控制的雪漫城。在这座城市附近，有 $N$ 座处于帝国控制下的塔楼。有 $N - 1$ 条道路连接这些塔楼，因此士兵可以通过这些道路从任意一座塔楼移动到另一座。

在军事上，战术深度是指所有塔楼中任意两座塔楼之间的最长路径。战术深度越大，这些塔楼就越稳定。

你的任务（如果你选择接受的话）：在每一轮中，乌弗里克会告诉你两条道路。你需要计算在摧毁这两条道路后，塔楼的战术深度。

输入格式

输入的第一行包含一个整数 $t$，表示测试用例的数量。接下来是 $t$ 个测试用例。

对于每个测试用例： 第一行包含两个整数 $N$（$N \le 100000$），表示塔楼的数量，以及 $Q$（$Q \le 100000$），表示询问的数量。

接下来的 $N - 1$ 行中，第 $i$ 行描述第 $i$ 条道路，包含三个整数 $u$、$v$ 和 $w$（$0 \le w \le 5000$），表示一条连接 $u$ 和 $v$ 且长度为 $w$ 的道路。

接下来的 $Q$ 行中，每行包含两个整数 $u$ 和 $v$，表示在这一轮中，第 $u$ 条道路和第 $v$ 条道路将被摧毁。保证 $u \neq v$。

输出格式

对于每个询问，输出战术深度。

样例

输入样例 1

1
8 3
2 1 7
3 1 7
4 2 5
5 2 6
4 6 3
7 2 8
1 8 2
4 6
2 3
5 6

输出样例 1

22
17
20