题目描述

守矢神社正在进行庞大的核工程。核工程有多个环节，比如采矿需要重金邀请荷取，插排需要找城管幽幽子盖章，重型搬运需要造非想天则……整个工程项目中的各个子工程之间的先后完成关系建立了一张拓扑图，其中一条边表示一条工程。为了方便描述，我们假定有 $n$ 个状态，状态之间由工程连接，接下来有 $m$ 条工程描述，每条描述由 $u,v,w$ 三个整数组成表示从 $u$ 状态必须完成持续 $w$ 时间的工程后才能进入 $v$ 状态。知道杜邦公司为什么大赚一笔吗？因为他们现提出了工程网络中的“关键路径”。现在帮助守矢神社，求他们工程网络从 $1$ 状态进入 $n$ 状态过程中的所有关键活动状态点的个数。如果对关键路径不熟悉或者看不懂题目的同学，请自行搜索并学习关键路径。

• 关键路径：图中从起点到终点最长的路径的长度（长度指的是路径上边的权重和）
• 关键活动：关键路径上的边
• 关键活动状态点：关键路径上的点

输入格式

第一行 $n,m$。接下来 $m$ 行每行三个数。具体内容如题目描述所述。

输出格式

一个数表示答案。

样例

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

4

数据范围

$n \le 200, m \le 1000$