시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 0 0 0 0.000%

문제

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.

예제 입력 1

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

예제 출력 1

1