Description

在伊辛格，巫师萨鲁曼借助魔法设立了一套连接 $n$ 座高塔的传送系统。具体来说，他创建了 $m$ 条单向通道，每条通道连接两座高塔。第 $i$ 条通道需要 $t_i$ 秒，表示一只兽人通过这条通道所需的时间。换句话说，萨鲁曼的传送系统可以表示为一个带权有向图。

在 12 月 15 日，萨鲁曼正坐在中央高塔 $\textit{奥桑克}$（Orthanc）中，他通过魔法石（palantír）收到索伦的消息：一份贵重的礼物已经运抵伊辛格入口塔附近。于是，萨鲁曼需要指示守卫选出一只兽人，让他沿着从入口塔到奥桑克的最短路径将礼物送达。

不幸的是，兽人……并不是很聪明。虽然他们能够拖运货物穿越通道，理论上也知道奥桑克的位置，但他们对于“最短路径”的理解实在是相当贫乏。为了简化操作，萨鲁曼决定在某些塔上放置一个巨大的闪光指示牌，写着“$\textbf{前往奥桑克 —— 此路}$”，并指向通往某条通道的方向。

萨鲁曼希望兽人尽可能快地到达奥桑克，因此指示牌只能指向某条通往奥桑克最短路径上的通道。形式化地说，如果塔 $u$ 上的指示牌指向通道 $\vec{a} = \overrightarrow{uv}$，那么必须满足：

$$\mathop{\overrightarrow{\mathrm{dist}}}(v, O) < +\infty \quad \text{且} \quad \mathop{\overrightarrow{\mathrm{dist}}}(u, O) = t_{\vec{a}} + \mathop{\overrightarrow{\mathrm{dist}}}(v, O)$$

其中，$\mathop{\overrightarrow{\mathrm{dist}}}(x, y)$ 表示从塔 $x$ 到塔 $y$ 的最短传送时间（若无法到达，则为 $+\infty$），$O$ 表示奥桑克所在的高塔编号，$u,v$ 分别为通道的起点和终点。

注意：萨鲁曼不会在奥桑克本身，也不会在从无法到达奥桑克的塔上设置指示牌。其余所有塔上，萨鲁曼将恰好设置一个指向某条合规通道的闪光指示牌。

即便如此，事情也并不总是顺利。每当一只兽人准备前往奥桑克时，他在经过每一座塔（除奥桑克外）时，要么选择跟随萨鲁曼设置的闪光指示牌前进，要么进行一次所谓的“$\textit{随意乱走}$”行为，即随机选择一条通道离开当前塔。

对于任意一只兽人，存在一个整数 $d$，表示他在整个传送过程中最多会进行 $d$ 次“随意乱走”。我们将这个值称为这只兽人的“$\textit{无能度}$”。

如果某一时刻兽人到达一座无法通往奥桑克的塔，那么他会发现该塔没有任何指示牌。此时，即便是最“有能”的兽人也会意识到任务失败，立即停止前进并等待救援。

萨鲁曼深知他的仆人们都不太聪明，所以他并不指望送货能很快完成，但他希望至少能保证送达。因此，有必要选择一只无能度尽可能大的兽人完成任务。但另一方面，真正聪明的兽人极为稀少，把他们从其他岗位调走会严重影响其他安排。

于是，给定伊辛格的传送系统，请你帮萨鲁曼找出一个最优策略安排指示牌，使得从入口塔（编号为 $1$）出发的兽人在无能度为 $d$ 的前提下，必然可以成功到达奥桑克（编号为 $n$）。请你求出这个最大可能的 $d$ 值。

Input Format

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 4 \cdot 10^5$，$0 \le m \le 4 \cdot 10^5$），分别表示塔的数量和通道的数量。

接下来 $m$ 行，每行包含三个整数 $u_i$、$v_i$ 和 $t_i$（$1 \le u_i, v_i \le n$，$1 \le t_i \le 10^6$），表示从塔 $u_i$ 到塔 $v_i$ 有一条传送时间为 $t_i$ 秒的单向通道。

可能存在多条通道连接相同的两个塔（同向或反向），也可能存在指向自身的通道（自环）。

塔 $1$ 为入口塔，塔 $n$ 为奥桑克。

Output Format

输出一个整数 $d$，表示满足题意的最大无能度。

如果任意无能度下都可以成功送达，输出 $n$；如果任意无能度下都无法送达，输出 $-1$。

5 7
1 3 5
4 5 2
3 4 3
1 5 9
4 2 8
5 2 11
3 5 5

2

6 6
1 2 5
2 3 9
1 4 11
2 1 1000000
5 3 15
5 6 1

-1

4 7
1 2 5
1 1 30
3 2 9
1 4 11
1 4 16
2 1 1000000
1 4 11

4

2 0

-1

6 7
1 2 5
2 3 9
1 6 11
2 1 1000000
1 5 9
5 6 2
5 4 4

1

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

1

3 2
1 2 1
1 3 1

0

Hint

样例图示如下：