Phát biểu bài toán

Cho ~ N ~ thành phố được đánh số từ ~ 1 ~ đến ~ N ~ (~ N \leq 100 ~) và ~ M ~ đoạn đường hai chiều nối trực tiếp giữa các thành phố. Nhiệm vụ là chọn một tour du lịch đi qua ít nhất ~ 3 ~ thành phố khác nhau. Tour bắt đầu và kết thúc tại cùng một thành phố và không được đi qua một thành phố nào hai lần (trừ lần đầu và lần cuối cùng). Tìm tổng chi phí nhỏ nhất của một tour thỏa mãn yêu cầu.Nếu không thể có tour thỏa mãn, xuất ra ~ 0 ~.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~ N ~, ~ M ~ (~ 1 \leq N \leq 100, 1 \leq M \leq 10,000 ~).
• ~ M ~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~ u, v, w ~:
  • ~ u, v ~ (~ 1 \leq u, v \leq N ~): Hai thành phố được nối trực tiếp.
  • ~ w ~ (~ 1 \leq w \leq 10,000 ~): Chi phí đi qua đoạn đường.

Kết quả ra

• Ghi ra tổng chi phí nhỏ nhất của một tour hợp lệ. Nếu không có tour hợp lệ, ghi ~ 0 ~.

Ví dụ

Input

5 7
1 4 1
4 1 300
1 3 10
3 1 10
4 2 16
2 5 20
5 3 25

Output

61

• Tour tốt nhất là: ~ 1 \to 4 \to 2 \to 5 \to 3 \to 1 ~ với tổng chi phí là ~ 1 + 16 + 20 + 25 + 10 = 61 ~.