[AdditionalFile5514.zip](file://AdditionalFile5514.zip?type=additional_file)

#5514. 「PA 2019 Final」Floyd-Warshall

标签: 传统 | 时间限制: 5000 ms | 内存限制: 256 MiB |

题目描述

题目译自 PA 2019 Final Floyd-Warshall

Mateusz 有一个包含 $n$ 个顶点的有向图，图中的边带有权重。他现在需要计算图中每对顶点之间的距离。为此，他决定使用 Floyd-Warshall 算法：

不幸的是，Mateusz 在代码中不小心调换了循环的顺序，导致他的算法实现错误！

在 Mateusz 的算法计算出的距离中，有多少是错误的？

输入格式

输入数据的第一行包含两个整数 $n$ 和 $m$ $(2 \leq n \leq 2000, 1 \leq m \leq 3000)$，分别表示图的顶点数和边数。

接下来的 $m$ 行描述边：每行包含三个整数 $u_{i}, v_{i}, w_{i}$ $(1 \leq u_{i}, v_{i} \leq n, u_{i} \neq v_{i}, 1 \leq w_{i} \leq 100000)$，表示第 $i$ 条边从顶点 $u_{i}$ 到顶点 $v_{i}$，权重为 $w_{i}$。每个有序对 $(u_{i}, v_{i})$ 在输入中最多出现一次。

输出格式

输出应包含一个整数，表示 Mateusz 的算法计算出的错误距离数量。

样例

输入

4 5
2 3 4
3 4 3
4 2 2
1 3 1
1 2 9

输出

1

以下依次展示了初始矩阵 $M$、正确实现生成的矩阵以及错误实现算法返回的矩阵。错误实现错误计算了 $M_{1,2}$ 的值。