时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
安徽芜湖有n个机场，一共有m条线路在空管部门报备。
每条线路单向连接两个机场，并且需要的通行时间每天都可能不一样。
具体来说，设目前是第x天，那么第i条线路所需要的通行时间为
。
一年一共有H天，也就是说，x取[0,H]中的整数。
现在大司马想从1号机场在一天内换乘任意多次航班前往n号机场，他总是选择用时最短的方式，现在他想知道哪一天需要花最长的时间。
每条线路单向连接两个机场，并且需要的通行时间每天都可能不一样。
具体来说，设目前是第x天，那么第i条线路所需要的通行时间为
一年一共有H天，也就是说，x取[0,H]中的整数。
现在大司马想从1号机场在一天内换乘任意多次航班前往n号机场，他总是选择用时最短的方式，现在他想知道哪一天需要花最长的时间。
输入描述:
每个测试点仅包含一组输入数据。
第一行三个整数，表示机场的数量，线路的数量和x的取值范围。
接下来m行，每行四个整数，表示一条线路从
机场单向前往
机场，并且第x天需要
同一对机场之间可能有多条航线，一条航线的起点和终点可能相同。
保证在[0,H]中的任意一天，每条航线的长度非负且不超过，且从1号机场可以到达n号机场。
输出描述:
输出一行一个整数，表示最长的用时。