T243203 前往 QWQ 星

**update: 数据已增强 ~~（卡掉了某chm~~** 大A 在领取了 大B 发的 [一笔画红包](https://www.luogu.com.cn/problem/T240771) 后兴奋地决定去 $\text{QWQ}$ 星旅行，大B 发的红包的总金额，将作为 大A 旅行过程中来回的预算路费 $T$。由于预算路费可能不够，所以 大A 想让你帮他算算出实际路费的最小值是多少。 你需在 $1$ 秒内帮他求出，因为去往 $\text{QWQ}$ 星的飞船还有 $1$ 秒就要出发了！他必须尽快规划好路线。

大A 从 $1$ 号空间站出发，而 $\text{QWQ}$ 星在 $M$ 号空间站附近，因此，大A 只需到 $M$ 号空间站，然后在乘坐免费的列车前往 $\text{QWQ}$ 星即可。大A 有预算路费 $T$ 元，可以搭乘的航班有 $N$ 次，空间站有 $M$ 个，大A 已事先在手机 $APP$ 上查询好了所有可搭乘的航班，每个航班有 $4$ 条属性，分别为：飞船号，起点空间站序号，终点空间站序号，票价。而你只需要求出最后需付的实际路费的最小值。

第一行 $1$ 个小数与 $2$ 个整数，分别为 $T,N,M$ 接下来的 $N$ 行，每行共 $1$ 个字符串, $2$ 个整数和 $1$ 个小数，分别为 $s , u , v , q$，分别代表 飞船号，起点空间站序号，终点空间站序号和票价。

输出共一行，包含一个整数，如果 大A 准备的路费不够，或者不能到达 $QWQ$ 星，就输出 ```-1```，否则输出最后需付的实际路费的最小值。实际路费需保留 $2$ 位小数后输出。

提示：可能两空间站内有多个航班，但保证方向不同且飞船号不同。并且返程时的航班与出发时相同，但是方向相反。 本题有多组测试点，分值不完全相同，以下为每组测试点的分值与计分方式： | | 测试点 | 分值 / 分 | 计分方式 | | -----------: | -----------: | -----------: | -----------: | | _Subtask #1_ | $1$~$9$ | $10$ | 最小值 | | _Subtask #2_ | $10$~$15$ | $30$ | 最小值 | | _Subtask #3_ | $16$~$20$ | $25$ | 最小值 | | _Subtask #4_ | $21$~$25$ | $35$ | 最小值 | 对于 $25\%$ 的数据，$0 ≤ N ≤ 20,2 ≤ M ≤ 20,0 ≤ T ≤ 2^{31}，0 ≤ q ≤ 2^{31}$ ，保证没有重复的飞船号。 对于 $100\%$ 的数据，$ 0 ≤ N ≤ 10^5, 2 ≤ M ≤ 10^5,0 ≤ T ≤ 2^{63},0 ≤ q ≤ 2^{63},1 ≤ u , v ≤ M$。