题目背景

小邓是某机房的一名运维。他在巡检时发现,机房里的网络链路远比想象中奇怪:不少链路是单向的,还有一些机器之间其实处在同一个局域网里,互传文件根本不花时间。

题目描述

在这个网络中,各台电脑并不是两两直接相连的,而是存在着若干条单向链路:存在从 $A$ 到 $B$ 的链路,并不意味着也存在从 $B$ 到 $A$ 的链路。并且,有的链路传输快,有的链路传输慢,所以不同链路上传输信息所花费的时间也各不相同。另外,如果 $A$ 到 $B$ 的链路与 $B$ 到 $A$ 的链路同时存在,那么 $A$ 和 $B$ 实际上处于同一个局域网内,可以通过本地传输,这样花费的传输时间为 $0$。

现在小邓把整张网络的构成情况都告诉了你,他想知道:从他正在使用的电脑(编号为 $1$)向目标服务器(编号为 $n$)传输一份文件,所需的最短传输时间是多少。

输入格式

第一行两个整数 $n,m$,表示共有 $n$ 台电脑和 $m$ 条连接关系。

接下来 $m$ 行,每行三个整数 $u,v,w$,表示从电脑 $u$ 到电脑 $v$ 单向传输信息的时间为 $w$。

输出格式

输出仅一行一个整数,即最短传输时间。

样例

3 2
1 2 1
2 3 1

2

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

3

提示

• 对于 $40\%$ 的数据,$1\leq n\leq 10^3$,$1\leq m\leq 10^4$;
• 对于 $70\%$ 的数据,$1\leq n\leq 5 \times 10^3$,$1\leq m\leq 10^5$;
• 对于 $100\%$ 的数据,$1\leq n\leq 2 \times 10^5$,$1\leq m\leq 10^6$。

保证答案在 int 范围内,且从 $1$ 号电脑一定可以到达 $n$ 号电脑。