Description

由于 A 学校生物实验室里那个不负责的数据分析员， 实验室的病毒威力被错误估算，导致了可怕的病毒泄漏，现在病毒即将在校园内传播开来。
校园里一共有 n 个建筑物， 生物实验室总是位于一号建筑物且在 0 时刻受到病毒入侵。 这 n个建筑物由 m 条单向道路相连（也有可能有建筑物被孤立）。每条道路有两个信息：它的长度， 它是多少年前修建的。 当一个建筑物被病毒入侵， 从被入侵的时刻起， 病毒会从所有由这个建筑物通向其他建筑物的道路按着这条道路的方向以 1 个单位每秒的速度行进。
校长得知这个事情后， 决定放弃这个学校逃跑。 校长总是位于编号为 n 的行政楼， 从零时刻开始需要共 T 秒来逃出行政楼， 且逃出行政楼即视为逃出了这个学校。 也就是说， 如果病毒入侵行政楼的时间不小于 T，则校长能够成功逃离。
有些时候，校长没有足够的时间逃离，因为病毒到达行政楼的时间太快了。
为了让校长能够逃离学校， 不得不拆除校园内的一些道路以延缓行政楼的被入侵时间（拆除道路视为在 0 时刻被拆的道路全部消失）。当然，如果使得病毒根本无法到达行政楼，也是可以的。
但是， 拆除道路会影响学校的历史气息， 且破坏程度定义为拆除的道路中最古老的一条的年龄。请求出保证校长能够安全撤离的情况下，最小的破坏程度。

Format

Input

第一行包含三个整数： n, m, T。
接下来 m 行，每行描述一条有向道路。每行 4 个整数， si, ti, Li, Yi，分别表示这条道路的起点，终点，长度，这条道路的年龄。

Output

如果不需要拆除任何道路，输出一行两个数： -1 和行政楼的被感染时刻（当然这个时刻大于等于 T），以空格隔开。
否则输出一行包含一个数：最小的破坏程度。

Sample 1

Input

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

Output

25
样例说明：
每条边上的黑字对应这条路的长度，红字对应年龄。校长将在第 15 秒逃出学校，如果不拆除任何道路，行政楼将在第 14 秒受到入侵。你可以拆除 4 到 5 的道路，使得行政楼免于入侵，这样的破坏程度是 50。但是最好的方法是拆掉 3 到 4 之间的道路，这样使得行政楼在第 19 秒受到入侵， 校长就可以逃离了。

Sample 2

Input

3 2 10
1 2 5 30
2 3 6 50

Output

-1 11

Limitation

2s, 131072KiB for each test case.

Hint

对于 60%的数据， n,m<=100.
对于 100%的数据， n<=20000, m<=100000.
数据保证在不拆除任何道路的情况下，从 1 号楼到 n 号楼一定存在路径。

Source

NOIP2017 太原五中模拟赛（四）Day1-T2