Cho một đồ thị vô hướng liên thông có ~n~ đỉnh và ~m~ cạnh, cạnh thứ ~i~ nối hai đỉnh ~u_i~ và ~v_i~ có độ dài ~w_i~.

Định nghĩa ~d(u, v) =~ độ dài đường đi ngắn nhất từ ~u~ đến ~v~

Yêu cầu: Với mỗi cạnh ~i~, bạn hãy đếm số cặp ~(u, v)~ sao cho ~d(u, v)~ tăng khi ta xóa cạnh ~i~

Lưu ý: Nếu một con đường khi bị phá đi làm việc di chuyển giữa hai giao lộ trở nên bất khả thi, con đường này cũng được coi là gây ảnh hưởng đến cặp giao lộ đó.

Input

• Dòng đầu chứa hai số nguyên dương ~n, m~ ~(n \le 500, m \le 10^4)~ là số đỉnh và số cạnh của đồ thị đã cho

• Dòng thứ ~i~ trong ~m~ dòng tiếp chứa ba số nguyên ~u_i, v_i, w_i~ ~(1 \le u_i, v_i \le n, 1 \le w_i \le 10^9)~ mô tả một cạnh của đồ thị

Output

Một dòng duy nhất chứa ~m~ số nguyên là các số đề yêu cầu

Scoring

Sample Input 1

4 4
1 2 1
2 4 10
1 3 5
3 4 7

Sample Output 1

3
2
2
1

Sample Input 2

4 3
1 2 22
1 3 7
1 4 97

Sample Output 2

3
3
3

Notes

Cạnh ~(1, 2)~ bị xoá sẽ làm độ dài đường đi ngắn nhất giữa ~1~ và ~2~ tăng từ ~1~ lên ~22~; đường đi ngắn nhất giữa ~1~ và ~4~ tăng từ ~11~ lên ~12~; đường đi ngắn nhất giữa ~2~ và ~3~ tăng từ ~6~ lên ~17~.

Cạnh ~(2, 4)~ bị xoá sẽ làm tăng độ dài đường đi ngắn nhất giữa ~1~ và ~4~; giữa ~2~ và ~4~.

Cạnh ~(1, 3)~ bị xoá sẽ làm tăng độ dài đường đi ngắn nhất giữa ~1~ và ~3~; giữa ~2~ và ~3~.

Cạnh ~(3, 4)~ bị xoá sẽ làm tăng độ dài đường đi ngắn nhất giữa ~3~ và ~4~.

Cạnh ~(1, 2)~ bị xoá khiến cho từ ~2~ không thể di chuyển tới ~1~, ~3~ và ~4~.

Tương tự với hai cạnh còn lại.