本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。
魔力之都可以抽象成一个$n$个节点、$m$条边的无向连通图（节点的编号从1至$n$）。我们依次用$l,a$描述一条边的长度、海拔。
作为季风气候的代表城市，魔力之都时常有雨水相伴，因此道路积水总是不可避免的。由于整个城市的排水系统连通，因此有积水的边一定是海拔相对最低的一些边。
我们用水位线来描述降雨的程度，它的意义是：所有海拔不超过水位线的边都是有积水的。
Yazid 是一名来自魔力之都的 OIer，刚参加完 ION2018 的他将踏上归程，回到他温暖的家。
Yazid 的家恰好在魔力之都的1号节点。对于接下来$Q$天，每一天 Yazid 都会告诉你他的出发点$v$，以及当天的水位线$p$。
每一天，Yazid 在出发点都拥有一辆车。这辆车由于一些故障不能经过有积水的边。
Yazid 可以在任意节点下车，这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。
需要特殊说明的是，第二天车会被重置，这意味着：
Yazid 非常讨厌在雨天步行，因此他希望在完成回家这一目标的同时，最小化他步行经过的边的总长度。请你帮助 Yazid 进行计算。
输入的第一行为一个非负整数$T$，表示数据的组数。接下来依次描述每组数据，对于每组数据：
对于输入中的每一行，如果该行包含多个数，则用单个空格将它们隔开。
依次输出各组数据的答案。对于每组数据：
Comet OJ1
4 3
1 2 50 1
2 3 100 2
3 4 50 1
5 0 2
3 0
2 1
4 1
3 1
3 20
50
200
50
1501
5 5
1 2 1 2
2 3 1 2
4 3 1 2
5 3 1 2
1 5 2 1
4 1 3
5 1
5 2
2 0
4 00
2
3
1【样例1解释】
第一天没有降水，Yazid 可以坐车直接回到家中。
第二天、第三天、第四天的积水情况相同，均为连接1，2号节点的边、连接3，4号点的边有积水。
对于第二天，Yazid 从2号点出发坐车只能去往3号节点，对回家没有帮助。因此 Yazid 只能纯靠徒步回家。
对于第三天，从4号节点出发的唯一一条边是有积水的，车也就变得无用了。Yazid 只能纯靠徒步回家。
对于第四天，Yazid 可以坐车先到达2号节点，再步行回家。
第五天所有的边都积水了，因此 Yazid 只能纯靠徒步回家。
【样例2解释】
第一天的答案是0，因此第二天的$v=(5+0-1)\bmod5+1=5,p=(2+0)\bmod(3+1)=2$。
第二天的答案是2，因此第三天的$v=(2+2-1)\bmod5+1=4,p=(0+2)\bmod(3+1)=2$。
第三天的答案是3，因此第四天的$v=(4+3-1)\bmod5+1=2,p=(0+3)\bmod(3+1)=3$。
【子任务】
所有测试点均保证$T \le 3$，所有测试点中的所有数据均满足如下限制：
为了方便你快速理解，我们在表格中使用了一些简单易懂的表述。在此，我们对这些内容作形式化的说明：
