该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

由于输入法十分的不听话，被 xxs 送到了北极

送货员：怎么进来的？

xxs：我想输入“收到”，他给我输出“受刀”，我真是受够他了

输入法：《世界孤立我任他奚落》

送货员：有这么几个路线我咋走划算啊，我生活费没多少了

xxs: 你自己像这般吧（输入法又双叒叕捣乱）

题目描述

为了快速把输入法送到北极，途中有 $m$ 条线路，有 $n$ 个中转站，只有到了中转站才可以转换路线，而且每条路线所需话费的钱数也不同

求始发点到北极花费最少的路线所需钱数

输入格式

输入一行 $n$ $m$，表示中转站的点数和线路条数 后 $m$ 行，每行一个 $x, y, z$，表示 $x$ 中转站到 $y$ 中转站的路线需 $z$ 元钱

输出格式

输出一行，求始发点到北极花费最少的路线所需钱数

当然，最后的中转站也就是所谓的“北极”

样例

6 8
1 2 1
1 3 3
2 5 5
2 4 2
3 5 2
3 4 1
5 6 5
4 6 3

6

提示

• $1\le n\le 10^3$
• $1\le n\le 10^4$
• $1\le x\le n$
• $1\le y\le n$
• $1\le z\le 10^4$