本题为问题的困难版本，两题的唯一区别在于询问的次数限制。在困难版本中，询问次数不多于 次。

在环扎阿越王国中有 个岛屿，岛屿之间一共存在 条双向道路连接。保证任意一条道路连接两个不同的岛屿，任意两个岛屿之间最多存在一条道路，任意两个岛屿之间可以通过道路相互抵达。
袋鼠将军被坎格鲁斯普雷打得落荒而逃，它逃到了编号为 的岛屿上，而袋鼠将军希望自己能够到达编号为 的岛屿并逃离环扎阿越王国。袋鼠将军可以通过道路在岛屿之间移动，但是，对于任意一条道路，每当袋鼠将军走过这条道路，都会损失一定的能量。袋鼠将军的初始能量为 。
幸运的是，在每个岛屿都存在着一定能量的补给。当袋鼠将军位于某个岛屿时，它都可以立即获得这个岛屿上的补给。但是，每个岛屿上的补给都只能被获取一次。
袋鼠将军会给你若干次询问，每次询问都会给定 与 。对于每次询问，请求出袋鼠将军在逃离环扎阿越王国时，最多剩下多少能量？
注意：袋鼠将军在到达编号为 的岛屿时，可以选择不立即逃离环扎阿越王国。也就是说，袋鼠将军可以在到达编号为 的岛屿后继续移动。但是，袋鼠将军最后必须位于编号为 的岛屿。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行输入一个整数 ，表示岛屿的个数。 
第二行输入  个整数 ，表示编号为  的岛屿上有  单位的能量。 
此后  行，第  行输入三个整数    ，表示第  条双向道路连接编号为  的岛屿与编号为  的岛屿，且每当袋鼠将军走过这条道路，它都会损失  单位的能量。 
第  行输入一个整数 ，表示询问的次数。 
此后  行，第  行输入两个整数 ，表示第  次询问中，袋鼠将军的起始位置为编号为  的岛屿，最终需要到达编号为  的岛屿。

除此之外，保证单个测试文件的  之和、 之和均不超过 。保证任意一条道路连接两个不同的岛屿，任意两个岛屿之间最多存在一条道路，任意两个岛屿之间可以通过道路相互抵达。

输出描述:

对于每组数据，新起一行输出  个整数 ，其中第  个整数  表示对于第  次询问，袋鼠将军在逃离环扎阿越王国时最多能剩下多少能量。

2
5
1 2 3 4 5
1 2 1
2 3 1
2 4 1
2 5 1
1
1 2
5
1 2 3 4 5
1 2 1
2 3 100
2 4 10
2 5 1
3
1 4
2 4
1 5

8
-1 -1 6

这两个样例中，岛屿的结构一致，如下图所示：



对于第一组测试数据，袋鼠将军可以按照如下路线移动：，袋鼠将军在编号为 , , , ,  的岛屿一共可以获得  单位的能量，而在经过上述路径时，一共损失了  单位的能量。需要注意的是，袋鼠将军每经过一次道路，都会损失一定的能量。袋鼠将军通过这种方式，最后剩余的能量为 。可以证明，这种方式是最优的。 

对于第二组测试数据的第一次询问，一种最优的路线是：；第三次询问中，一种最优的路线是：。

备注:

注意：对于 Python 选手，单链的情况可能导致递归爆栈，请注意代码实现。