|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|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.
Unfortunately Radewoosh messed up loops order and his algorithm became incorrect!
Incorrect implementation of Floyd-Warshall's algorithm.
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.
4 5 2 3 4 3 4 3 4 2 2 1 3 1 1 2 9