当前没有测试数据。

2.删边问题

题目描述

给出一张$n$个点，$m$条边的有向图，每条边有长度和价值，要删掉一些边使得起点$1$到终点$n$的最短路不低于给定的$T$，要在保证这个前提下使得删掉的边中的最大的价值最小，求这个最小值。

输入格式

第一行包含三个整数：$n$，$m$，$T$。接下来$m$行。

每行描述一条有向道路。

每行$4$个整数，$u$，$v$，$len$，$val$，分别表示这条道路的起点，终点，长度，这条道路的价值。

输出格式

如果不需要删边，输出一行两个数：$-1$和最短路径长度（当然，这个值大于等于$T$），以空格隔开。否则输出一行包含一个数：最小的价值。

数据范围与提示

• 对于$20\%$的数据，$n$，$m \leq 10$；
• 对于$60\%$的数据，$n$，$m \leq 100$；
• 对于$100\%$的数据，$n \leq 20000$，$m \leq 100000$；
• 数据保证在不拆除任何道路的情况下，从$1$号楼到$n$号楼一定存在路径。

样例

5 5 15 
1 2 6 35 
2 4 8 40 
1 3 6 45 
3 4 3 25 
4 5 5 50

25

3 2 10 
1 2 5 30 
2 3 6 50

-1 11