你好！我是你的OI金牌教练。

我们已经学习了图论中的BFS/DFS（连通性）、并查集（集合合并）以及拓扑排序（依赖关系）。

今天，我们将穿越到繁荣的唐朝，结合**“玄奘西行取经”**的历史背景，来攻克图论中最为核心、应用最广泛的算法之一——最短路径问题 (Shortest Path Problem)。

这道题是 GESP 6级 的高频考点，也是 CSP-J/S 的必修课。它与之前的知识点有极强的递进关系：

• 在“战国合纵连横”中，我们用 BFS 解决了无权图（边权看作1）的最短距离问题。
• 今天，我们要解决的是带权图（边有不同的长度/代价）的最短路径问题。这就需要引入Dijkstra 算法。

第一部分：背景知识讲解

1. 玄奘西行 (Xuanzang's Journey to the West)

唐太宗贞观元年（627年），高僧玄奘从长安出发，独自一人西行前往天竺（今印度）求取佛经。他途经西域、中亚，历经“九九八十一难”，穿越了八百里莫贺延碛（大沙漠），最终到达那烂陀寺。

2. 关隘与路途代价

在西行的路途中，玄奘需要经过许多国家和关隘（如高昌国、龟兹国）。

• 节点 (Node)：代表国家或补给站。
• 边 (Edge)：代表两个地点之间的道路。
• 权值 (Weight)：不同道路的艰险程度不同。有的路平坦，只需消耗 1 袋水；有的路是沙漠或雪山，需要消耗 10 袋水。

3. 算法递进：从 BFS 到 Dijkstra

• 回顾 BFS：如果每条路的长度都是 1，我们可以用队列进行 BFS，一层一层向外扩展，第一次到达某点时就是最短路。
• 遇到问题：如果路的长度不一样（有的长有的短），普通的队列就失效了。因为“先到的点”不一定“代价最小”。
• 解决方案 (Dijkstra)：
  • 贪心策略：每次从“当前已知距离最小”的未访问节点出发，去更新它的邻居。
  • 优先队列：为了快速找到“当前距离最小”的点，我们不能用普通队列，而要用优先队列 (Priority Queue)（小根堆）。

第二部分：题目内容

题目名称：西行之路 (Journey to the West)

题目描述

玄奘法师准备从长安（编号 $1$）出发，前往天竺（编号 $N$）。 西域的地图上有 $N$ 个重要的国家或据点，编号为 $1$ 到 $N$。 这些据点之间由 $M$ 条单向道路连接。第 $i$ 条道路从 $u_i$ 通向 $v_i$，通过这条路需要消耗 $w_i$ 的饮用水。

由于沙漠环境恶劣，玄奘希望规划一条从起点 $1$ 到终点 $N$ 的路线，使得总消耗的饮用水最少。

请你编写程序，计算出从 $1$ 号据点到达 $N$ 号据点的最小总消耗。如果无法到达，请输出 -1。

输入格式

第一行包含两个正整数 $N, M$。

• $N$ 表示据点数量。
• $M$ 表示道路数量。

接下来 $M$ 行，每行包含三个正整数 $u, v, w$。

• 表示存在一条从 $u$ 到 $v$ 的单向道路，消耗为 $w$。

输出格式

输出一行一个整数。

• 如果能到达，输出最小消耗。
• 如果无法到达，输出 -1。

输入输出样例 #1

输入：

5 6
1 2 2
1 3 10
2 3 3
2 4 8
3 5 1
4 5 5

输出：

6

样例 #1 解释： 求 1 到 5 的最短路：

• 路径 A: $1 \to 3 \to 5$，消耗 $10 + 1 = 11$。
• 路径 B: $1 \to 2 \to 4 \to 5$，消耗 $2 + 8 + 5 = 15$。
• 路径 C: $1 \to 2 \to 3 \to 5$，消耗 $2 + 3 + 1 = 6$。 最优解是路径 C，总消耗 6。

输入输出样例 #2

输入：

3 2
1 2 5
2 1 5

输出：

-1

样例 #2 解释： 只有 1 和 2 互相连通，无法到达 3。

数据范围

对于 $100\%$ 的数据：

• $1 \le N \le 10^5$
• $1 \le M \le 2 \times 10^5$
• $1 \le w_i \le 1000$
• 保证起点是 1，终点是 $N$。