#P18308. Packet Transmission

Packet Transmission

Packet Transmission

给定一棵有 NN 个节点的树,表示由路由器和通信信道组成的网络。每个节点是一台路由器,每条边是一条连接两台路由器的信道。第 ii 条边连接 ui,viu_i,v_i,沿任一方向通过该信道传输一个数据包均需要 tit_i 单位时间。

路由器可以存储任意数量的数据包,数据包可以在路由器中等待任意长时间。一台路由器可以同时通过不同的信道发送多个数据包,但一条信道同一时刻至多传输一个数据包,两个方向共用这一限制。一旦开始沿某条边传输,一个数据包必须经过该边所需的完整时间才能到达另一端。

对每次询问,需要从时刻 00 开始同时完成两个数据包的传输:第一个数据包从 s1s_1 送到 d1d_1,第二个数据包从 s2s_2 送到 d2d_2。可以安排数据包在路由器中等待。请最小化两个数据包到达各自目的地的时刻的最大值,输出这个最小值。

各次询问独立,网络不会被修改。数据包的起点和终点可以相同,此时它在时刻 00 已到达目的地。数据包同时位于同一台路由器不构成冲突;如果前一个传输恰好结束,下一次传输可以立即开始。

输入格式

第一行包含一个整数 TT,表示测试用例数。

对每个测试用例:

  • 第一行包含两个整数 N,QN,Q。
  • 接下来 N−1N-1 行,每行包含三个整数 ui,vi,tiu_i,v_i,t_i,描述一条边。
  • 接下来 QQ 行,每行包含四个整数 s1,d1,s2,d2s_1,d_1,s_2,d_2,描述一次询问。

所有边构成一棵树。

输出格式

对每次询问,输出一行一个整数,表示两个数据包都到达目的地所需的最短时间。

数据范围

  • 1≤T≤10001\le T\le1000。
  • 1≤N,Q≤1000001\le N,Q\le100000。
  • 1≤ui,vi≤N1\le u_i,v_i\le N,ui≠viu_i\ne v_i。
  • 1≤ti≤1091\le t_i\le10^9。
  • 1≤s1,d1,s2,d2≤N1\le s_1,d_1,s_2,d_2\le N。
  • 所有测试用例的 NN 之和不超过 500000500000,QQ 之和不超过 500000500000。

答案可能超过 32 位整数范围。

样例

输入

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

输出

7
15
24
1
3