Mỗi khi đến tiết thể dục, các học sinh nam lại tụ họp trên sân cỏ để đá bóng. Hiện tại có ~2n~ học sinh trên sân, cần chia ra hai đội, mỗi đội ~n~ người để đá bóng. Các học sinh được đánh số từ ~1~ đến ~2n~.

Có ~m~ cặp học sinh là bạn bè của nhau, họ có xu hướng phối hợp với nhau tốt hơn là hai người không phải bạn bè. Mỗi cặp bạn bè sẽ có một chỉ số gọi là sức mạnh tình bạn.

Ta định nghĩa sức mạnh của một đội là tổng sức mạnh tình bạn nằm trong đội đó. Để trận đấu diễn ra một cách công bằng nhất, chênh lệch sức mạnh giữa hai đội phải nhỏ nhất có thể.

Yêu cầu: Cho biết ~n~ và ~m~ cặp bạn bè, tìm cách chia đội sao cho chênh lệch sức mạnh giữa hai đội là nhỏ nhất.

Input

• Dòng đầu tiên gồm hai số nguyên ~n, m\ (1 \leq n \leq 200,\ 0 \leq m \leq n \times (2n - 1))~.

• ~m~ dòng tiếp theo, mỗi dòng gồm ba số nguyên ~u,\ v,\ w\ (1 \leq u < v \leq 2n)~ thể hiện một cặp bạn bè.

Dữ liệu đảm bảo tổng sức mạnh bạn bè không vượt quá ~2n \times 2n~.

Output

• In ra chênh lệch nhỏ nhất có thể đạt được nếu chia đội một cách tối ưu.

Subtask

• ~20\%~ số test có ~n \leq 8~.

• ~60\%~ số test có ~n \leq 50~.

• ~20\%~ số test không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

2

Note

Một cách chia thỏa mãn đề bài là đội thứ nhất gồm các học sinh ~1,\ 3~ và đội thứ hai gồm các học sinh ~2,\ 4~. Chênh lệch sức mạnh giữa hai đội sẽ là ~|1 - 3| = 2~.