题目描述

最短路径查询

给定一个包含多个节点和边的有向图，每条边都有一个正的权重。请你编写程序，计算从起点（节点1）到终点（节点N）的最短路径长度。如果从起点无法到达终点，则输出-1。

输入描述

输入格式：

第一行包含两个整数N和M，分别表示图中节点的数量和边的数量。

接下来M行，每行包含三个整数u、v、w，表示存在一条从节点u到节点v的有向边，这条边的权重为w。

输出格式

输出格式：

输出一个整数，表示从节点1到节点N的最短路径长度。如果无法到达，则输出-1。

输入样例

4 5
1 2 2
1 3 5
2 3 1
2 4 4
3 4 3

输出样例

6

数据范围

数据范围：

• 1 ≤ N ≤ 1000
• 1 ≤ M ≤ 10000
• 1 ≤ u, v ≤ N
• 1 ≤ w ≤ 100