题目描述

  Zjr为了成为APEX高手，苦心钻研了游戏中的行进路线。游戏地图中存在$n$个不同的地区，相互之间由无向路径连接。他想要从落地点(编号为$1$)经过合理路径后到达决赛圈(编号为$n$)，但是由于毒圈的限制，他必须在$T$时间内完成目标。现在他利用Ly的快速侦察能力，掌握了$m$条路径各自的物资丰富程度$w_i$，以及通过它们所需要花费的时间$t_i$。Zjr为了发展的更好，所以他只会选取物资丰富程度大于等于$W$的路径，输出满足条件的最大$W$。

输入格式

多组输入。

第一行输入$c(1≤c≤5)$代表测试样例数量。

第二行输入$n(2≤n≤10^5)$, $m(1≤m≤5 \times 10^5)$, $T(1≤T≤10^8)$分别代表点的数量,边的数量和限制时间。

接下来$m$行分别输入$u$, $v$ $(1≤u, v≤n)$, $w(1≤w≤10^9)$, $t(1≤t≤10^9)$, 代表$u$点和$v$点之间存在一条物资丰富程度$w$，耗时$t$的路径。

数据保证$\sum n≤10^5, \sum m≤5×10^5$。

输出格式

对于每个测试用例，按照输入中给出的顺序，打印一行，其中包含从落地点到决赛圈的路径的最大资源丰富度，并考虑时间约束。落地点与决赛圈之间始终至少存在一条路径满足条件。

样例

1
2 1 5
1 2 10 5

10

来源

2022 HGNU-SWUT暑假联合集训