20588번 - Floyd-Warshall 출처다국어

Radewoosh has $n$-vertex directed weighted graph. He needs to determine distances between all pairs of vertices. He decided to use Floyd-Warshall's algorithm for that.

Correct implementation of Floyd-Warshall's algorithm.

1. $M$ -- $n \times n$ matrix. Initially: $$M_{i,j} = \begin{cases}  0, & \text{if } i = j \\  w_{i,j}, & \text{if there exists an edge from $i$ to $j$ with weight $w_{i,j}$} \\  \infty & \text{otherwise}  \end{cases}$$
2. for $x$ = $1, 2, 3, \dots, n$ do
3.     for $y$ = $1, 2, 3, \dots, n$ do
4.         for $z$ = $1, 2, 3, \dots, n$ do
5.             $M_{y,z} \leftarrow\min(M_{y,z}, M_{y,x} + M_{x,z})$

Unfortunately Radewoosh messed up loops order and his algorithm became incorrect!

Incorrect implementation of Floyd-Warshall's algorithm.

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

How many distances determined by Radewoosh's algorithm will be incorrect?

The first line of input contains two integers $n$ and $m$ ($2 \le n \le 2\,000$, $1 \le m \le 3\,000$) denoting number of vertices and number of edges in our graph, respectively.

Each of the following $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$) denoting that $i$-th edge goes from vertex $u_i$ to vertex $v_i$ and has weight $w_i$.

No ordered pair $(u_i, v_i)$ will be given more than once.

Output should contain one number --- number of ordered pairs of vertices which have its distance computed incorrectly by Radewoosh's algorithm.