您居住在一个由 $$$n$$$ 个十字路口和连接一些对十字路口的 $$$m$$$ 街道组成的城市。您可以在每条街道上向任一方向行驶。没有两条街道连接同一对交叉路口,也没有街道将交叉路口连接到自身。您可以从任何其他十字路口到达任何十字路口,也可能会经过一些其他十字路口。
每分钟,您可以在路口 $$$u_i$$$ 上车,行驶 $$$l_{i1}$$$ 分钟到达路口 $$$v_i$$$。相反,您可以在 $$$l_{i1}$$$ 分钟内从交叉路口 $$$v_i$$$ 行驶到交叉路口 $$$u_i$$$。您只能在十字路口上下车。如果您当前在十字路口,则只能在该十字路口上车。
您还可以沿着每条街道步行,需要 $$$l_{i2} > l_{i1}$$$ 分钟。
您可以在交叉路口停车。
您住在 $$$1$$$ 路口。今天您在时间 $$$0$$$ 起床,并且您在编号为 $$$n$$$ 的路口安排了一项重要活动,您必须在时间 $$$t_0$$$ 之前到达该路口。您还计划进行一次通话,通话时间从 $$$t_1$$$ 到 $$$t_2$$$ 分钟 ($$$t_1 < t_2 < t_0$$$)。
通话期间,您不能乘坐公交车,但可以沿任何街道步行、停靠或留在家中。您可以在 $$$t_1$$$ 分钟下车,并在 $$$t_2$$$ 分钟再次上车。
因为你想保证充足的睡眠,所以你很好奇——你要多晚才能离开家,有时间打电话,同时还不至于迟到?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。以下是测试用例的描述。
每个测试用例的第一行包含两个整数 $$$n$$$, $$$m$$$ ($$$2 \le n \le 10^5, 1 \le m \le 10^5$$$) — 城市中十字路口和街道的数量。
每个测试用例的第二行包含三个整数 $$$t_0$$$、$$$t_1$$$、$$$t_2$$$ ($$$1 \le t_1 < t_2 < t_0 \le 10^9$$$) — 分别是事件的开始时间、电话的开始时间和结束时间。
每个测试用例接下来的 $$$m$$$ 行包含街道的描述。
第 $$$i$$$ 行包含四个整数 $$$u_i$$$, $$$v_i$$$, $$$l_{i1}$$$, $$$l_{i2}$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$, $$$1 \le l_{i1} < l_{i2} \le 10^9$$$) — 第 $$$i$$$ 条街道所连接的路口数量,以及沿该街道乘坐公交车和步行的时间。保证没有两条街道连接同一对交叉路口,并且可以从任何其他交叉路口到达任何交叉路口。
保证所有测试用例的 $$$n$$$ 值的总和不超过 $$$10^5$$$。还保证所有测试用例的 $$$m$$$ 值的总和不超过 $$$10^5$$$。
输出
对于每个测试用例,输出一个整数 - 您可以离开家以便有时间打电话且不会迟到的最晚时间。如果无法准时到达活动地点,则输出-1。
示例
输入 #1
7 5 5 100 20 80 1 5 30 100 1 2 20 50 2 3 20 50 3 4 20 50 4 5 20 50 2 1 100 50 60 1 2 55 110 4 4 100 40 60 1 2 30 100 2 4 30 100 1 3 20 50 3 4 20 50 3 3 100 80 90 1 2 1 10 2 3 10 50 1 3 20 21 3 2 58 55 57 2 1 1 3 2 3 3 4 2 1 12 9 10 2 1 6 10 5 5 8 5 6 2 1 1 8 2 3 4 8 4 2 2 4 5 3 3 4 4 5 2 6
输出 #1
0 -1 60 80 53 3 2