Hạo có một đồ thị gồm \(N\) đỉnh và \(M\) cạnh, mỗi cạnh được gán một trọng số. Hạo biết rằng đồ thị này chứa một số đường đi Hamilton (đường đi qua tất cả các đỉnh đúng một lần). Anh ấy thách bạn của mình tìm phần tử nhỏ nhất trong mảng lưu trữ sức mạnh của tất cả các đường đi Hamilton trong đồ thị.

Sức mạnh của một đường đi Hamilton được định nghĩa là tổng trọng số của các cạnh trong đường đi đó. Nhưng Hạo không biết đáp án. Hãy giúp Hạo giải bài toán này.

Đầu vào

• Dòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách, biểu diễn \(N\) và \(M\).
• M dòng tiếp theo, mỗi dòng chứa ba số nguyên X, Y, và Z, biểu thị có một cạnh giữa đỉnh \(X\) và \(Y\) với trọng số \(Z\).

Đầu ra

• In ra một dòng chứa kết quả — phần tử nhỏ nhất trong mảng sức mạnh của các đường đi Hamilton.

Ràng buộc

• \(1 <= N <= 10\)
• \(1 <= M <= 20\)
• \(1 <= X, Y <= N\)
• \(1 <= Z <= 100\)

Input 1

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

Output 1

7