题目描述

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

现在要求从 111 走到 n 。问最少需要多少时间。

输入格式

第一行两个整数 n 和 m，表示有多少个城市和多少条道路。

接下来 m 行，每行两个整数 u 、v 、c ，即有一条从 u 到 v 需要花费时间 c 的道路。

输出格式

一行一个整数，即从 1 到 n 最少需要多少时间。

样例

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

22

数据规模

• 70% 的数据，1≤n,m≤1000
• 100% 的数据，1≤n,m≤100000