Floyd-Warshall

Radewoosh는 정점이 $n$개인 방향 가중 그래프를 가지고 있다. 그는 모든 정점 쌍 사이의 거리를 구해야 해서 Floyd-Warshall 알고리즘을 쓰기로 했다.

Floyd-Warshall 알고리즘을 올바르게 구현하면 다음과 같다.

1. $M$은 $n \times n$ 행렬이다. 초기값은 다음과 같다.

$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. $x = 1, 2, 3, \dots, n$에 대해 다음을 반복한다.
3. $y = 1, 2, 3, \dots, n$에 대해 다음을 반복한다.
4. $z = 1, 2, 3, \dots, n$에 대해 다음을 반복한다.
5. $M_{y,z} \leftarrow \min(M_{y,z}, M_{y,x} + M_{x,z})$

Radewoosh가 반복문의 순서를 잘못 바꾸는 바람에 그의 알고리즘은 틀리게 되었다.

잘못 구현한 알고리즘은 다음과 같다.

1. $M$은 위에서 정의한 $n \times n$ 행렬이다.
2. $y = 1, 2, 3, \dots, n$에 대해 다음을 반복한다.
3. $z = 1, 2, 3, \dots, n$에 대해 다음을 반복한다.
4. $x = 1, 2, 3, \dots, n$에 대해 다음을 반복한다.
5. $M_{y,z} \leftarrow \min(M_{y,z}, M_{y,x} + M_{x,z})$

Radewoosh의 알고리즘으로 거리를 잘못 구하는 정점 순서쌍은 몇 개인가?

첫 줄에 정점의 개수 $n$과 간선의 개수 $m$이 주어진다 ($2 \le n \le 2\,000$, $1 \le m \le 3\,000$).

이어지는 $m$개의 줄에는 정수 $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$). 이는 $i$번째 간선이 $u_i$에서 $v_i$로 가며 가중치가 $w_i$라는 뜻이다. 같은 순서쌍 $(u_i, v_i)$는 두 번 주어지지 않는다.

Radewoosh의 알고리즘으로 거리를 잘못 계산하는 정점 순서쌍의 개수를 한 줄에 출력한다.