给定一个代表路由器和信道的连通网络树。每个节点代表一个路由器，每条边代表连接两个路由器的信道。这些信道用于将数据包从一个路由器传输到其相邻的路由器之一，传输遵循 TCP/IP 协议。边上标记有 $t_i$，表示将数据包从 $u_i$ 传输到 $v_i$（或反之）所需的时间（单位任意）。

此外，每个路由器都有足够的存储容量来存储任意数量的数据包，它们可以无限期地存储数据包，并且可以通过不同的信道同时传输多个数据包。这意味着你不能通过当前已被另一传输占用的信道发送数据包。

你的任务是同时发送两个数据包，一个从 $s_1$ 路由器发送到 $d_1$ 路由器，另一个从 $s_2$ 路由器发送到 $d_2$ 路由器。确定最优传输策略，以最小化两个数据包从源点到达终点所需的最大时间。

输入格式

输入的第一行包含一个整数 $T(1 \le T \le 1000)$，表示测试用例的数量。每个测试用例的第一行包含两个整数 $N$ 和 $Q(1 \le N, Q \le 100000)$。接下来有 $N-1$ 行输入，每行包含三个整数 $u_i, v_i, t_i(1 \le u_i, v_i \le N, u_i \neq v_i, 1 \le t_i \le 10^9)$，表示树的第 $i$ 条边。

随后有 $Q$ 行，每行包含四个整数 $s_1, d_1, s_2, d_2(1 \le s_1, d_1, s_2, d_2 \le N)$，表示两个数据包的源路由器和目标路由器。保证所有测试用例中 $N$ 的总和不超过 $500000$，$Q$ 的总和不超过 $500000$。

输出格式

对于每个查询，请使用最优传输策略以最小化两个数据包送达的最大时间，并将该最小时间打印在单独的一行中。

样例

输入 1

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

输出 1

7
15
24
1
3