Floyd-Warshall

Radewoosh has a directed weighted graph with $n$ vertices. He needs the distance between every pair of vertices, so he decided to use the Floyd-Warshall algorithm.

A correct implementation of Floyd-Warshall is as follows.

1. $M$ is an $n \times n$ matrix. Its initial values are:

$M_{i,j} = \begin{cases} 0, & \text{if } i = j \\ w_{i,j}, & \text{if there is an edge from } i \text{ to } j \text{ with weight } w_{i,j} \\ \infty & \text{otherwise} \end{cases}$

2. For $x = 1, 2, 3, \dots, n$ do the following.
3. For $y = 1, 2, 3, \dots, n$ do the following.
4. For $z = 1, 2, 3, \dots, n$ do the following.
5. $M_{y,z} \leftarrow \min(M_{y,z}, M_{y,x} + M_{x,z})$

Radewoosh changed the order of the loops, and his algorithm is now incorrect.

His incorrect implementation is as follows.

1. $M$ is the $n \times n$ matrix defined above.
2. For $y = 1, 2, 3, \dots, n$ do the following.
3. For $z = 1, 2, 3, \dots, n$ do the following.
4. For $x = 1, 2, 3, \dots, n$ do the following.
5. $M_{y,z} \leftarrow \min(M_{y,z}, M_{y,x} + M_{x,z})$

How many ordered pairs of vertices have a distance that Radewoosh's algorithm computes incorrectly?

The first line contains two integers $n$ and $m$ ($2 \le n \le 2\,000$, $1 \le m \le 3\,000$), the number of vertices and the number of edges.

Each of the next $m$ lines contains three integers $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$). This means the $i$-th edge goes from $u_i$ to $v_i$ with weight $w_i$. No ordered pair $(u_i, v_i)$ appears more than once.

Print one integer: the number of ordered pairs of vertices whose distance is computed incorrectly by Radewoosh's algorithm.