AT_joisc2008_nightman 夜警 (Nightman)

在一个神秘的夜晚，您被要求探索一个由 $N$ 个房间组成的迷宫。这些房间通过双向通道连接。每条通道有一个通行时间，表示在这条通道上旅行所需的时间。 起初，您站在起始房间。您的目标是沿着迷宫旅行，并成功到达终点房间。在旅途中，您可能要访问每个房间多次。请注意，可能存在多条不同的路径可供选择。 为了完成任务，您需要找到从起点到终点的最短时间路径。

- 第一行包含两个整数 $N$ 和 $M$，分别表示房间的数量和通道的数量。 - 接下来的 $M$ 行，每行包含三个整数 $u$，$v$ 和 $t$，表示连接两个房间 $u$ 和 $v$ 的通道以及通过这条通道需要的时间 $t$。

输出一个整数，表示从起始房间到终点房间的最短通行时间。如果没有路径能到达终点房间，输出 `-1`。

- 房间数量 $1 \leq N \leq 10^5$ - 通道数量 $1 \leq M \leq 10^6$ - 时间 $1 \leq t \leq 10^9$ 在一些情况下，可能会出现多个具有相同时间的最短路径。在这些情况下，您只需输出一个最短时间即可，无需考虑路径的多少。解决这类问题时，常用的算法包括 Dijkstra 算法或 Bellman-Ford 算法。确保您的程序在大数据量下运行良好。 **本翻译由 AI 自动生成**