Radewoosh 有一个包含 $n$ 个顶点的带权有向图。他需要确定所有顶点对之间的距离。 他决定使用 Floyd-Warshall 算法来解决这个问题。

Floyd-Warshall 算法的正确实现如下：

• $M$ 为 $n \times n$ 矩阵。初始时： $$M_{i,j} = \begin{cases} 0, & \text{if } i = j \\ w_{i,j}, & \text{if there exists an edge from } i \text{ to } j \text{ with weight } w_{i,j} \\ \infty & \text{otherwise} \end{cases}$$
• for $x = 1, 2, 3, \dots, n$ do
  • for $y = 1, 2, 3, \dots, n$ do
    • for $z = 1, 2, 3, \dots, n$ do
      • $M_{y,z} \leftarrow \min(M_{y,z}, M_{y,x} + M_{x,z})$

不幸的是，Radewoosh 把循环顺序弄乱了，导致他的算法变得不正确！ Floyd-Warshall 算法的错误实现如下：

• $M$ 为如上定义的 $n \times n$ 矩阵。
• for $y = 1, 2, 3, \dots, n$ do
  • for $z = 1, 2, 3, \dots, n$ do
    • for $x = 1, 2, 3, \dots, n$ do
      • $M_{y,z} \leftarrow \min(M_{y,z}, M_{y,x} + M_{x,z})$

Radewoosh 的算法计算出的距离中有多少个是不正确的？

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 2\,000, 1 \le m \le 3\,000$)，分别表示图中顶点的数量和边的数量。接下来的 $m$ 行，每行包含三个整数 $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le w_i \le 100\,000$)，表示第 $i$ 条边从顶点 $u_i$ 指向顶点 $v_i$，权重为 $w_i$。不会给出重复的有序对 $(u_i, v_i)$。

输出格式

输出应包含一个数字——被 Radewoosh 的算法错误计算出距离的有序顶点对的数量。

样例

输入 1

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

输出 1

1

说明 1

样例测试的解释：在此我们展示了以下内容：初始矩阵 $M$、由正确算法生成的矩阵以及由 Radewoosh 的实现生成的矩阵。错误版本产生了一个错误 —— $M_{1,2}$。