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.

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.

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 $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$.

3 2
1 2 1
2 3 1

0

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