Background

KOBE 牢大我想你了

Description

KOBE 是一位黑曼巴，可是有一天他打球打太远了，回去要很长的一段时间。他要从第 $1$ 个球场坐直升机回第 $N$ 个球场。他找到了你，求你帮他找到最快的路径，使他可以最快的回到球场。

Input

输入共 $M+1$ 行，第一行包括两个数 $N,M$ 即球场个数，路径个数。 接下来 $M$ 行，每行三个整数，$X$ ，$Y$ , $Z$ ，即从第 $X$ 个球场到第 $Y$ 个球场要花 $Z$ 的时间(每条路是单向的)。

Output

输出只有一行，即所需最短时间。

Samples

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

6

Limitation

对于 $100 \%$ 的数据，$2 \le N \le 10000$，$1 \le M \le 20000$，$0 \le V \le 100,000$； $WHAT$ $CAN$ $I$ $SAY$ $,$ $manba$ $out$