### 问题描述 城市 $A$ 正在规划其公交系统，希望为市民提供从城市的西部（起点 $s$）到城市的东部（终点 $t$）的便捷交通服务。城市有多条公交路线，每条公交路线连接两个公交站台，每条路线可能会需要不同的时间。 为了提供多种选择，市政府希望找到从 $s$ 到 $t$ 的前 $k$ 个最短的公交路线。其中公交站的编号从 $1$ 开始，且注意规划的路线不能多次通过同一个公交站台，题目保证每两个站台之间的直接相连的最多只有一条公交线路。 你的任务是帮助城市找到这 $k$ 条最短的公交路线。 ### 输入格式 第一行包含五个整数：$n$、$m$、$k$、$s$ 和 $t$，分别表示城市的公交站点数量、公交路线数量和需要找到的最短路线数量，以及起点和终点。 接下来的 $m$ 行，每行包含三个整数：$u$、$v$ 和 $w$，表示从公交站点 $u$ 到公交站点 $v$ 有一条路线，其旅行时间为 $w$ 分钟。 ### 输出格式 输出 $k$ 行，每行一个整数，表示从 $s$ 到 $t$ 的前 $k$ 个最短路线的旅行时间。如果少于 $k$ 条路线，则只从小到大输出存在的路线的旅行时间即可。 ### 样例输入 ``` 5 7 3 1 5 1 2 10 1 3 15 2 4 20 3 4 30 2 5 25 4 5 20 3 5 35 ``` ### 样例输出 ``` 35 50 50 ``` ### 样例说明 从 $1$ 到 $5$ 的三条最短路线分别为： 1. $1 \rightarrow 2 \rightarrow 5$，总旅行时间为 $35$ 分钟。 2. $1 \rightarrow 2 \rightarrow 4 \rightarrow 5$，总旅行时间为 $50$ 分钟。 3. $1 \rightarrow 3 \rightarrow 5$，总旅行时间为 $50$ 分钟。 ### 测评数据规模 对于 $40$% 的数据，$n \leq 10$，$m \leq 50$，$k \leq 3$。 对于 $80$% 的数据，$n \leq 100$，$m \leq 1000$，$k \leq 10$。 对于 $100$% 的数据，$n \leq 500$，$m \leq 10000$，$k \leq 50$。