U385791 输入法去北极

## 由于输入法十分的不听话，被 xxs 送到了北极 送货员：怎么进来的？ xxs：我想输入“收到”，他给我输出“受刀”，我真是受够他了 输入法：《世界孤立我任他奚落》 送货员：有这么几个路线我咋走划算啊，我生活费没多少了 xxs: 你自己像这般吧（输入法又双叒叕捣乱）

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

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

输出一行，求始发点到北极花费最少的路线所需钱数 当然，最后的中转站也就是所谓的“北极”

* $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$ 本题可以使用 SPFA、Floyd，保证数据不超时