#ABC051D. Candidates of No Shortest Paths

Candidates of No Shortest Paths

Problem Statement

You are given an undirected connected weighted graph with NN vertices and MM edges that contains neither self-loops nor double edges. The ii-th (1iM)(1≤i≤M) edge connects vertex aia_i​ and vertex bib_i​ with a distance of cic_i​. Here, a self-loop is an edge where ai=bi(1iM)a_i​=b_i​(1≤i≤M), and double edges are two edges where (ai,bi)=(aj,bj)(a_i​,b_i​)=(a_j​,b_j​) or (ai,bi)=(bj,aj)(1i<jM)(a_i​,b_i​)=(b_j​,a_j​)(1≤i<j≤M). A connected graph is a graph where there is a path between every pair of different vertices. Find the number of the edges that are not contained in any shortest path between any pair of different vertices.

Constraints

  • 2N1002≤N≤100
  • N1Mmin(N(N1)/2,1000)N-1≤M≤min(N(N−1)/2,1000)
  • 1ai,biN1≤a_i​,b_i​≤N
  • 1ci10001≤c_i​≤1000
  • cic_i​ is an integer.
  • The given graph contains neither self-loops nor double edges.
  • The given graph is connected.

Input

The input is given from Standard Input in the following format:

N   M
a1  b1  c1
..
aM  bM  cM

Output

Print the number of the edges in the graph that are not contained in any shortest path between any pair of different vertices.

Samples

3 3
1 2 1
1 3 1
2 3 3
1

In the given graph, the shortest paths between all pairs of different vertices are as follows:

  • The shortest path from vertex 11 to vertex 22 is: vertex 11 → vertex 22, with the length of 11.
  • The shortest path from vertex 11 to vertex 33 is: vertex 11 → vertex 33, with the length of 11.
  • The shortest path from vertex 22 to vertex 11 is: vertex 22 → vertex 11, with the length of 11.
  • The shortest path from vertex 22 to vertex 33 is: vertex 22 → vertex 11 → vertex 33, with the length of 22.
  • The shortest path from vertex 33 to vertex 11 is: vertex 33 → vertex 11, with the length of 11.
  • The shortest path from vertex 33 to vertex 22 is: vertex 33 → vertex 11 → vertex 22, with the length of 22.

Thus, the only edge that is not contained in any shortest path, is the edge of length 33 connecting vertex 22 and vertex 33, hence the output should be 11.

3 2
1 2 1
2 3 1
0

Every edge is contained in some shortest path between some pair of different vertices.