#572. 最短路

最短路

题目描述

nn 个 城市,从1到 nn 给他们编号,它们之间由一些单向道路(即一条道路只能从一个方向走向另一个方向,反之不行)相连,每条路还有一个花费 c(i)c(i) ,表示通过第i条边需要花费 c(i)c(i) 的时间。

现在要求从 11 走到 nn 。问最少需要多少时间。

输入格式

第一行两个整数 nnmm,表示有多少个城市和多少条道路。

接下来 mm 行,每行两个整数 uuvvcc ,即有一条从 uuvv 需要花费时间 cc 的道路。

输出格式

一行一个整数,即从 11nn最少需要多少时间。

样例

输入样例

4 5
1 2 20
1 3 10
3 2 5
2 4 7
3 4 15

输出数据

22

数据范围与提示

70%70\% 的数据,1n,m10001 \le n,m \le 1000

100%100\% 的数据,1n,m1000001 \le n,m \le 100000