Problem Statement

You are given a simple connected undirected graph with N vertices and M edges.
Edge i connects Vertex A_i and Vertex B_i, and has a length of C_i.
Let us delete some number of edges while satisfying the conditions below. Find the maximum number of edges that can be deleted.

• The graph is still connected after the deletion.
• For every pair of vertices (s, t), the distance between s and t remains the same before and after the deletion.

Input

Input is given from Standard Input in the following format:
N M
A_1 B_1 C_1
A_2 B_2 C_2
$\vdots$
A_M B_M C_M

Output

Print the answer.

Constraints

• $2 \leq N \leq 300$
• $N-1 \leq M \leq \frac{N(N-1)}{2}$
• $1 \leq A_i \lt B_i \leq N$
• $1 \leq C_i \leq 10^9$
• $(A_i, B_i) \neq (A_j, B_j)$ if $i \neq j$.
• The given graph is connected.
• All values in input are integers.

Sample Input 1

3 3
1 2 2
2 3 3
1 3 6

Sample Output 1

1

The distance between each pair of vertices before the deletion is as follows.

• The distance between Vertex 1 and Vertex 2 is 2.
• The distance between Vertex 1 and Vertex 3 is 5.
• The distance between Vertex 2 and Vertex 3 is 3.

Deleting Edge 3 does not affect the distance between any pair of vertices. It is impossible to delete two or more edges while satisfying the condition, so the answer is 1.

Sample Input 2

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

Sample Output 2

0

No edge can be deleted.

Sample Input 3

5 10
1 2 71
1 3 9
1 4 82
1 5 64
2 3 22
2 4 99
2 5 1
3 4 24
3 5 18
4 5 10

Sample Output 3

5

见题面 Input 部分

见题面 Output 部分