题目描述

在 Isengard，巫师 Saruman 借助魔法，在 $n$ 座塔之间建立了一套运输系统。具体来说，他建立了 $m$ 条单向通道。第 $i$ 条通道附带一个数 $t_i$，表示半兽人通过这条通道需要的秒数。

因此，Saruman 的运输系统可以表示为一张带正权的有向图。

12 月 15 日，坐在中央高塔 Orthanc 中的 Saruman 通过真知晶球收到 Sauron 的消息：一份贵重礼物已经到达 Isengard 的入口塔附近。Saruman 需要命令驻军挑选一名半兽人，让他沿入口塔到 Orthanc 的最短路径运送礼物。

不幸的是，半兽人并不聪明。虽然他们能够沿通道搬运货物，也至少知道 Orthanc 在哪里，但他们对“最短路径”这个概念理解得很差。

为了简化任务，Saruman 会在一些塔上放置巨大的闪烁指示牌，上面写着：

TO ORTHANC — THIS WAY

并指向该塔的一条出边。

Saruman 希望半兽人尽快到达 Orthanc，因此指示牌只能指向某条属于到 Orthanc 的最短路径的通道。

形式化地，塔 $u$ 上的指示牌可以指向通道

$$\vec a=\overrightarrow{uv}$$

当且仅当

$$\operatorname{dist}(v,O)<+\infty$$

且

$$\operatorname{dist}(u,O)=t_{\vec a}+\operatorname{dist}(v,O)。$$

其中：

• $\operatorname{dist}(x,y)$ 表示从塔 $x$ 到塔 $y$ 的最短时间；若不存在有向路径，则该距离为 $+\infty$；
• $O$ 表示 Orthanc；
• $u,v$ 分别是通道 $\vec a$ 的起点和终点。

Saruman 不会在 Orthanc 上放置指示牌，也不会在无法到达 Orthanc 的塔上放置指示牌。在其余每座塔上，他恰好放置一个指示牌。

即使如此，系统仍不完美。半兽人在前往 Orthanc 的过程中，每次到达一座不是 Orthanc 的塔时，可以：

• 按指示牌选择通道；
• 或者进行一次 Saruman 所说的“闲逛”：从该塔所有出边中完全随机选择一条。

对于每名半兽人，都存在一个整数 $d$，使得当他接到前往 Orthanc 的命令时，整个旅途中进行“闲逛”的次数不会超过 $d$。我们礼貌地把这个数称为该半兽人的 无能程度。

有时，半兽人可能到达一座无法通过有向路径到达 Orthanc 的塔。在这种不幸情况下，即使是最有能力的半兽人也会发现那里没有指示牌，意识到任务失败，立刻停止并等待救援。

Saruman 只要求礼物最终能够送达。他希望选用尽可能不称职的半兽人，以免抽调稀有的能干半兽人影响其他工作。

给定运输系统，请求出最大的整数 $d$，使得 Saruman 可以放置指示牌，从而保证一名无能程度恰好为 $d$ 的半兽人从入口塔出发后，无论每次闲逛时随机选择哪条通道，都一定能够最终到达 Orthanc。

输入格式

第一行包含两个整数 $n,m$：

$$2\le n\le4\cdot10^5,$$ $$0\le m\le4\cdot10^5,$$

分别表示塔的数量和单向通道数量。

接下来 $m$ 行，每行包含三个整数 $u_i,v_i,t_i$：

$$1\le u_i,v_i\le n,$$ $$1\le t_i\le10^6,$$

表示一条从 $u_i$ 指向 $v_i$、通过时间为 $t_i$ 秒的通道。

图中允许出现：

• 自环；
• 重边；
• 两个方向均存在的对称通道。

入口塔编号为 $1$，Orthanc 编号为 $n$。

输出格式

输出一个整数 $d$，表示能够保证完成运送任务的半兽人的最大无能程度。

• 若无论无能程度多大都可以保证成功，输出 $n$；
• 若即使无能程度为 $0$ 也无法保证成功，输出 -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