在艾辛格（Isengard），巫师萨鲁曼（Saruman）利用一些魔法，组织了一个连接 $n$ 座塔的运输系统。具体来说，他创建了 $m$ 条单向通道，每条通道连接两座塔。每条通道 $i$ 都有一个关联的数值 $t_i$，表示兽人沿该通道行进所需的时间（以秒为单位）。换句话说，萨鲁曼的运输系统可以用一个带权有向图来表示。

12月15日，坐在名为欧散克（Orthanc）的中塔里的萨鲁曼通过真知晶球（palantir）收到萨鲁曼的消息，称一份贵重的礼物已经到达艾辛格的入口塔附近。因此，萨鲁曼需要指示守卫挑选一名兽人，带着礼物沿从入口塔到欧散克的某条最短路径行进。

不幸的是，兽人……并不是很聪明。虽然他们能够沿着运输系统中的通道搬运货物，并且（原则上）知道欧散克在哪里，但兽人对“最短路径”这一概念的理解非常贫乏。为了让大家的生活更轻松，萨鲁曼在一些塔上放置了一个巨大的闪烁指针，上面写着“去欧散克——走这边”，并指向从该塔出发的其中一条通道。萨鲁曼希望兽人能尽可能快地到达欧散克，因此，闪烁指针只能指向位于通往欧散克的某条最短路径上的通道。

形式化地，塔 $u$ 上的闪烁指针可以指向通道 $\vec{a} = \vec{uv}$，当且仅当 $\text{dist}(v, O) < +\infty$ 且 $\text{dist}(u, O) = t_{\vec{a}} + \text{dist}(v, O)$。这里，我们用 $\text{dist}(x, y)$ 表示从塔 $x$ 到塔 $y$ 所需的最短时间（如果从 $x$ 到 $y$ 没有有向路径，则为 $+\infty$），$O$ 表示欧散克塔，$u$ 和 $v$ 分别表示通道 $\vec{a}$ 的起点和终点。注意，萨鲁曼不会在欧散克上放置闪烁指针，也不会在任何无法到达欧散克的塔上放置指针。在其余的每座塔上，他都会放置且仅放置一个闪烁指针。

这仍然不能完美运作。在前往欧散克的过程中，每当兽人靠近某座塔（欧散克除外）时，兽人可以选择带有萨鲁曼标志的标记通道，或者进行一些“闲逛”（萨鲁曼语），即兽人完全随机地选择一条出通道。对于任何兽人，都存在一个整数 $d$，使得当他们接到去欧散克的命令时，在通勤过程中，兽人选择“闲逛”的次数永远不会超过 $d$ 次。我们将这个确切的数字称为该兽人的“无能度”。

注意，在某些时刻，兽人可能会发现自己处于一座无法到达欧散克的塔附近。在这种不幸的情况下，即使是最不称职的兽人也会发现塔上没有闪烁指针，从而意识到任务失败，立即停止并等待救援。

萨鲁曼知道他的仆人头脑并不灵光，所以他不指望礼物能很快送到，但他至少希望任务能成功。因此，指派一名尽可能称职的兽人来完成这项任务是有意义的；另一方面，称职的兽人很稀缺，将他们从当前的工作中抽调出来可能会完全扰乱那些工作。因此，给定艾辛格运输系统的描述，求出最大的整数 $d$，使得萨鲁曼可以通过放置闪烁指针，让一个无能度为 $d$ 的兽人被指派从入口塔运送礼物，并保证能够成功完成任务，到达欧散克。

输入格式

第一行包含两个整数 $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$）。同一对塔之间可能有多条通道，方向任意，也可能存在从塔指向自身的通道——换句话说，允许存在自环、重边和对称的通道对。

入口塔编号为 1，欧散克编号为 $n$。

输出格式

输出一个整数 $d$ —— 能够保证完成运送任务的兽人的最大无能度。如果无论无能度是多少都能完成任务，输出 $n$（塔的数量）。反之，如果无论无能度是多少都无法完成任务，输出 $-1$。

样例

样例 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

样例 2

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

-1

样例 3

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

4

样例 4

2 0

-1

样例 5

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

1

样例 6

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

1

样例 7

3 2
1 2 1
1 3 1

0