G. 旅途中的通话

每个测试点的时间限制：$4$ 秒
内存限制：$256$ MB

你住在一个由 $n$ 个路口和 $m$ 条街道组成的城市中。每条街道连接两个路口，你可以在街道上双向通行。没有两条街道连接同一对路口，也没有街道连接同一个路口。你可以从任意一个路口到达任意另一个路口（可能经过其他路口）。

在每一分钟，你可以在路口 $u_i$ 上车，乘坐公交车 $l_{i1}$ 分钟后到达路口 $v_i$。反过来，你也可以从路口 $v_i$ 乘车 $l_{i1}$ 分钟到达路口 $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$。

示例

输入：

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

输出：

0
-1
60
80
53
3
2