### 问题描述 随着全球化的快速发展，城市间的交通网络也越来越复杂。假设现在有一个大型城市，由 $n$ 个交通枢纽（站点）组成。每个交通枢纽可以通过公路、高铁或飞机与其他交通枢纽相连接。每种交通工具都有其特定的出行费用和时间。 假设你作为一个交通规划专家，需要为一个旅行社设计一种最优的出行方案。这个方案的目标是，在给定的预算内，用最短的时间从起点站 $a$ 出发，通过一系列的站点，到达终点站 $b$。 给定交通网络的描述，你的任务是找出一个最短的旅行时间，但是必须在预算之内。 输入包括交通枢纽的数量 $n$，交通线路的数量 $m$，起点站 $a$ 和终点站 $b$，预算 $p$，以及 $m$ 个交通线路的描述。每条交通线路的描述包括起点站、终点站、交通方式、所需时间和费用。 ### 输入格式 第一行：四个整数，分别为 $n, m, a, b$ 和 $p$，$(1 \le a, b \le n, a \neq b)$. 接下来的 $m$ 行，每行描述一条交通线路。包括五个整数：起点站 $x$，终点站 $y$，交通方式 $t$（$1$：公路，$2$：高铁，$3$：飞机)，所需时间 $time$ 和费用 $cost$。 ### 输出格式 输出一个整数，表示从 $a$ 到 $b$ 的最短旅行时间。如果无法在预算内到达，输出 $-1$。 ### 样例输入 ``` 5 7 1 5 100 1 2 1 3 10 1 3 2 2 50 2 3 1 2 10 2 4 2 1 40 3 4 1 3 20 3 5 3 1 60 4 5 1 2 10 ``` ### 样例输出 ``` 6 ``` ### 样例说明 在这个例子中，一种最短时间的方案是：从 $1$ 乘高铁到 $3$，然后从 $3$ 飞到 $5$，总费用为 $110$。但是超出了 $100$ 的预算。 所以另一个方案是：从 $1$ 经过公路到 $2$，然后从 $2$ 乘高铁到 $4$，最后从 $4$ 经过公路到 $5$，总时间为 $5$，费用为 $60$，没有超出预算。 ### 测评数据规模 对于 $40$% 的数据，$1 \le n, m \le 10$。 对于 $80$% 的数据，$1 \le n \le 50$，$1 \le m \le 500$。 对于 $100$% 的数据，$1 \le n \le 100$，$1 \le m \le 1000$，$1 \le time, cost \le 1000$，$1 \le p \le 10^4$。