题目描述

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

现在要求从 $1$ 走到 $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 \le n,m \le 1000$

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