题目描述
给出一张 $n$ 个点，$m$ 条边的有向图，每条边有长度和价值，要删掉一些边使得起点 $1$ 到终点 $n$ 的最短路不低于给定的 $T$ ，要在保证这个前提下使得删掉的边中的最大的价值最小，求这个最小值。
输入
第一行包含三个整数：$n,m,T$。接下来 $m$ 行。
每行描述一条有向道路。
每行 $4$ 个整数 $u,v,len,val$，分别表示这条道路的起点，终点，长度，这条道路的价值。
输出
如果不需要删边，输出一行两个数： $-1$ 和最短路径长度（当然，这个值大于等于 $T$ ），以空格隔开。否则输出一行包含一个数：最小的价值。
样例输入输出
输入#1
复制
5 5 15
1 2 6 35
2 4 8 40
1 3 6 45
3 4 3 25
4 5 5 50
输入#2
复制
3 2 10
1 2 5 30
2 3 6 50
提示
对于 $10\%$ 的数据，$n,m \leq 10$；
对于 $60\%$ 的数据，$n,m \leq 100$；
对于 $100\%$ 的数据，$n \leq 20000$，$m \leq 100000$ 。
数据保证在不拆除任何道路的情况下，从 $1$ 号楼到 $n$ 号楼一定存在路径