← 返回题目列表

Codeforces · 2000/G

G. 旅途中打电话

中文机器翻译题面 查看原题

您居住在一个由 $$$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