题目描述

农场有 $N$ 个牧场（$1$ 号为谷仓，$N$ 号为目的地），$M$ 条单向下坡路径（编号小的牧场更高，只能从高走向低）。两姐妹同时从 $1$ 号出发、同时到达 $N$ 号。

每条路有长度，两人速度相同。问她们沿不同路线、用相同时间到达的方案中，相关的统计量（如方案数/最短等长路径，见数据）。

输入格式

第一行 $N$、$M$；接下来 $M$ 行，每行描述一条路径（两端牧场与长度）。

输出格式

一行一个整数，表示结果。

输入示例 1

3 3
1 3 1 2
1 2 1 2
2 3 1 2

输出示例 1

2

题意细节见题目数据。

约束条件

• 路径均为下坡单向