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.

제한

힌트