P095 Dijkstra 单源最短路

题目描述

给定 n 个点 m 条边的带权有向图（边权为正），求从点 1 到点 n 的最短路径长度。

若无路径，输出 -1。

输入格式

第一行 n, m（2 \le n \le 10^5，1 \le m \le 2 \times 10^5）。
接下来 m 行，每行 u, v, w（1 \le u, v \le n，1 \le w \le 10^4）。

输出格式

从 1 到 n 的最短路径长度，或 -1。

样例

输入:
4 4
1 2 1
2 3 1
3 4 1
1 4 5

输出: 3