题目描述

给定 $n$ 个点 $m$ 条边的有向图，每条边有个边权，代表经过这条边需要花费的时间，我们只能从编号小的点走到编号大的点，问从 1 号点走到 $n$ 号点最少需要花费多少时间？

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示存在一条从 $u$ 到 $v$ 的边权为 $w$ 的有向边。

保证存在一条 1 到 $n$ 的路径。

输出格式

输出一个数，表示答案。

Samples

8 10
1 2 1
1 3 2
2 4 3
2 5 4
3 5 2
3 6 4
4 7 2
5 7 1
6 7 3
7 8 2

7

数据规模

对于所有数据，保证 $1≤n≤10^3,1≤m≤10^3,1≤u<v≤n,1≤w≤10^3$