Analyzing the Incorrect Floyd-Warshall Algorithm

Given a simple directed weighted graph with ( n ) nodes, we define a matrix ( M ) as follows: [ M_{i,j} = \begin{cases} 0, & \text{if } i=j,
w_{i,j}, & \text{if there is a directed edge } i\to j \text{ with weight } w_{i,j},
\infty, & \text{otherwise.} \end{cases} ]

The correct Floyd-Warshall algorithm uses the loop order:

[ \begin{array}{ll} \hline \textbf{Algorithm 1}: & \text{Correct Floyd-Warshall} \ \hline 1 & \textbf{Input: } n \times n \text{ matrix } M \text{ as defined above} \ 2 & \textbf{for } k = 1,2,\ldots,n \textbf{ do} \ 3 & \quad \textbf{for } i = 1,2,\ldots,n \textbf{ do} \ 4 & \quad\quad \textbf{for } j = 1,2,\ldots,n \textbf{ do} \ 5 & \quad\quad\quad M_{i,j} \gets \min(M_{i,j}, M_{i,k}+M_{k,j}) \ \hline \end{array} ]

However, Radewoosh mistakenly implemented the algorithm with the following loop order:

[ \begin{array}{ll} \hline \textbf{Algorithm 2}: & \text{Incorrect Floyd-Warshall} \ \hline 1 & \textbf{Input: } n \times n \text{ matrix } M \text{ as defined above} \ 2 & \textbf{for } i = 1,2,\ldots,n \textbf{ do} \ 3 & \quad \textbf{for } j = 1,2,\ldots,n \textbf{ do} \ 4 & \quad\quad \textbf{for } k = 1,2,\ldots,n \textbf{ do} \ 5 & \quad\quad\quad M_{i,j} \gets \min(M_{i,j}, M_{i,k}+M_{k,j}) \ \hline \end{array} ]

Let the correct shortest path distance from node ( x ) to node ( y ) be ( \operatorname{dist}(x,y) ), and let the distance computed by Algorithm 2 be ( \operatorname{dist}'(x,y) ).

Your task is to compute the number of ordered pairs ( (x,y) ) such that ( \operatorname{dist}(x,y) \neq \operatorname{dist}'(x,y) ).

Note: Treat ( \infty ) as a sufficiently large value. The graph is given in a 1-indexed format.

inputFormat

The first line contains two integers ( n ) and ( m ) representing the number of nodes and edges, respectively. Each of the next ( m ) lines contains three integers ( u\ v\ w ) indicating a directed edge from node ( u ) to node ( v ) with weight ( w ).

outputFormat

Output a single integer: the number of ordered pairs ( (x,y) ) for which the correct shortest path distance ( \operatorname{dist}(x,y) ) differs from the distance computed by the incorrect algorithm ( \operatorname{dist}'(x,y) ).

sample

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

1