Cho một đơn đồ thị liên thông gồm \(N\) đỉnh và \(M\) cạnh. Cạnh thứ \(i\) nối đỉnh hai đỉnh \(u_i\) và đỉnh \(v_i\) với trọng số \(w_i\). Một cạnh được gọi là vô dụng nếu sau khi xóa nó đi mà:

• Đồ thị vẫn liên thông.
• Với mọi cặp đỉnh \((s,t)\), độ dài đường đi ngắn nhất từ \(s\) đến \(t\) vẫn không thay đổi.

Bạn hãy lập trình tính số lượng cạnh vô dụng trong đồ thị đã cho nhé!

Input

• Dòng đầu chứa hai số nguyên dương \(N\) và \(M\) \(\left(2\le N\le 300, 1\le M\le \dfrac{N(N-1)}{2}\right)\).
• Dòng thứ \(i\) trong \(M\) dòng tiếp theo chứa ba số nguyên \(u_i\), \(v_i\), và \(w_i\) \(\left(1\le u_i < v_i\le N, 1\le w_i\le 10^9\right)\).

Output

• In ra số lượng cạnh vô dụng trong đồ thị đã cho.

Ví dụ

Sample input 01

3 3
1 2 3
2 3 4
1 3 8

Sample output 01

1

Giải thích

Cạnh \((1,3)\) là một cạnh vô dụng.