Problem Statement

You are given an undirected connected weighted graph with N vertices and M edges that contains neither self-loops nor double edges.
The i-th (1≤i≤M) edge connects vertex a_i and vertex b_i with a distance of c_i.
Here, a self-loop is an edge where a_i = b_i (1≤i≤M), and double edges are two edges where (a_i,b_i)=(a_j,b_j) or (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.

Input

Output

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

Constraints

• 2≤N≤100
• N-1≤M≤min(N(N-1)/2,1000)
• 1≤a_i,b_i≤N
• 1≤c_i≤1000
• c_i is an integer.
• The given graph contains neither self-loops nor double edges.
• The given graph is connected.

Sample Input 1

3 3
1 2 1
1 3 1
2 3 3

Sample Output 1

1

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

• The shortest path from vertex 1 to vertex 2 is: vertex 1 → vertex 2, with the length of 1.
• The shortest path from vertex 1 to vertex 3 is: vertex 1 → vertex 3, with the length of 1.
• The shortest path from vertex 2 to vertex 1 is: vertex 2 → vertex 1, with the length of 1.
• The shortest path from vertex 2 to vertex 3 is: vertex 2 → vertex 1 → vertex 3, with the length of 2.
• The shortest path from vertex 3 to vertex 1 is: vertex 3 → vertex 1, with the length of 1.
• The shortest path from vertex 3 to vertex 2 is: vertex 3 → vertex 1 → vertex 2, with the length of 2.

Thus, the only edge that is not contained in any shortest path, is the edge of length 3 connecting vertex 2 and vertex 3, hence the output should be 1.

Sample Input 2

3 2
1 2 1
2 3 1

Sample Output 2

0

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

见题面 Input 部分

见题面 Output 部分