CF2000G.Call During the Journey

你所居住的城市由 $n$ 个交叉路口和连接几对交叉路口的 $m$ 条街道组成。您可以在每条街道上向任一方向前进。没有两条街道连接同一对交叉路口，也没有一条街道只连接一个交叉路口。您可以从任何一个交叉路口到达另一个交叉路口，但可能会经过其他一些交叉路口。

每分钟，你可以在路口 $u_i$ 登上一辆公交车，然后行驶 $l_{i1}$ 分钟到达路口 $v_i$ 。相反，您可以在 $l_{i1}$ 分钟内从路口 $v_i$ 到达路口 $u_i$ 。您只能在交叉路口上下车。只有当您正在某交叉路口时，才能在该交叉路口登上公共汽车。

您也可以沿着每条街道步行，这需要 $l_{i2} \gt l_{i1}$ 分钟。

您可以在十字路口停车。

您住在十字路口编号 $1$ 处。今天您在 $0$ 点起床，在路口编号 $n$ 处有一个重要活动安排，您必须在 $t_0$ 点之前到达。你还计划打一个电话，通话时间为 $t_1$ 至 $t_2$ 分钟（ $t_1 \lt t_2 \lt 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 \lt t_1 \lt t_2 \lt 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} \lt l_{i2} \le 10^9$ ）--即由第 $i$ 条街道连接的十字路口的编号，以及沿街乘坐公交车和步行所需的时间。保证没有两条街道连接同一对交叉路口，并且可以从任何一个交叉路口到达另一个交叉路口。

保证所有测试用例中 $n$ 的值之和不超过 $10^5$ 。同时保证所有测试用例中 $m$ 的值之和不超过 $10^5$ 。

对于每个测试用例，输出一个整数--您离开家的最晚时间，以便有时间讲电话而不会迟到。如果您不能按时到达活动地点，则输出 -1。