U436607 星际旅行

鸢解开密码之后，梦之空的公司也已经掌握了星际旅行的技术。鸢处在的星系由很多个星球组成，每个星球都有一个独特的编号（$1$ 到 $N$）。每个星球都有一些可以直接到达的星球，希望国航天部将这些连接称为星际通道。鸢还发现，这些通道都是单向的，鸢的飞船开始时位于星球 1，她的目标是穿梭到星球 $N$。

- 第一行包含两个整数 $N,M$ 分别表示星球的数量和星际通道的数量。 - 第二行包含一个整数 $E$，表示飞船开始时的能量。 - 接下来的 $M$ 行，每行包含三个整数 $a$，$b$ 和 $c$，表示存在一条从星球 $a$ 到星球 $b$ 的通道，需要消耗$c$的能量。

- 输出一个整数，表示到达星球 $N$ 所需的最小能量消耗，如果无法到达，则输出 $-1$。

### 样例解释 - 在 **样例$#1$** 中，飞船开始时的能量是10。最优的路径是从星球1到星球2（消耗2点能量），然后从星球2到星球4（消耗2点能量），最后从星球4到星球5（消耗4点能量）。总共消耗的能量是8，所以输出8。 ### 提示 - 这个问题可以通过图论和最短路径算法来解决，例如**Dijkstra** 算法或者 **Bellman-Ford** 算法。你需要构建一个图，其中节点表示星球，边表示星际通道，边的权重表示通过通道需要消耗的能量。然后，你需要找出从星球1到星球 $N$ 的最短路径（也就是能量消耗最少的路径）。 - 然而，每次通过星际通道都需要消耗能量，不同的通道需要的能量可能不同。你的飞船开始时有一定的能量，你需要找出一条能量消耗最少的路径，如果没有足够的能量到达星球 $N$，那么输出-1。 ### 注意 - 如果没有足够的能量到达星球 $N$，那么输出 $-1$。这意味着，如果所有可能的路径的能量消耗都超过了飞船开始时的能量，那么就无法到达星球 $N$。 - 即使有很多路径，但是输入任何字符后回车都会输出 $-1$（详见 **样例#2**） > 特殊情况：当 $n = 1$ 时，如果输入字符后不做任何处理会直接输出 0。 ### 其他 #### 对于 $100\%$ 的数据 - 星球的数量 $n$：$1 ≤ n ≤ 10^5$ - 星际通道的数量 $m$：$1 ≤ m ≤ 10^5$ - 飞船开始时的能量 $e$：$1 ≤ e ≤ 10^9$ - 星际通道的起始星球 $a$ 和目标星球 $b$：$1 ≤ a, b ≤ n$ - 通过星际通道需要消耗的能量 $c$：$1 ≤ c ≤ 10^7$