Mạng lưới giao thông gồm có n nút, giữa các nút có thể có đường nối hai chiều và không có hai đường cùng nối hai nút. Có tất cả m đường , mỗi đường thuộc môt trong ba loại đánh số 1, 2, 3. Người số 1 chỉ có thể đi trên đường 1, 3; người số hai chỉ có thể đi trên 2,3.
Hệ thống giao thông đảm bảo cho cả người 1 lẫn 2 đều có thể đi từ một nút đến một nút bất kì. Hãy tìm cách bỏ đi một số nhiều nhất các đường nối sao cho tính chất liên thông trên vẫn được đảm bảo.

Input:

• Dòng đầu tiên ghi hai số n, m (n ≤ 500 ; m ≤ 10000)
• m dòng tiếp theo mỗi dòng ghi 3 số u, v, k cho biết có đường nối đinh u với đinh v thuộc loại k (k=1,2,3)

Output:

• Dòng đầu tiên ghi P là số lượng đường nhiều nhất có thể loại

Ví dụ:

INPUT

5 8
1 3 3
1 5 2
1 2 3
2 5 1
2 3 3
2 4 2
3 4 1
4 5 1

OUTPUT

2