Cho một đơn đồ thị vô hướng gồm 𝑛 đỉnh, 𝑚 cạnh, mỗi cạnh được tô màu xanh hoặc màu đỏ. Mỗi lượt bạn được chọn một đường đi (không nhất thiết phải là đường đi đơn), mỗi khi đi qua một cạnh, màu trên cạnh đó sẽ đổi màu (từ xanh sang đỏ, từ đỏ về xanh).

Yêu cầu: Thực hiện ít lượt nhất để đưa tất cả các cạnh về màu xanh.

Input

• Dòng đầu chứa hai số nguyên 𝑛, 𝑚 (𝑛, 𝑚 ≤ 10^5);

• Tiếp theo là 𝑚 dòng, mỗi dòng chứa ba số 𝑖, 𝑗, 𝑐𝑖𝑗, trong đó 𝑐𝑖𝑗 bằng 0 tức là cạnh (𝑖, 𝑗) tô màu xanh, ngược lại 𝑐𝑖𝑗 bằng 1 tức là cạnh (𝑖, 𝑗) tô màu đỏ.

Output

• Ghi ra số lượt ít nhất để đưa tất cả các cạnh về màu xanh.

Sample Input

4 3 
1 2 1 
2 3 1 
3 1 1 
1 4 1

Sample Output

1