Cho bản đồ giao thông vô hướng liên thông gồm \(N\) địa điểm và \(M\) con đường kết nối với nhau. Cần tìm chu trình ngắn nhất đi qua ít nhất 3 địa điểm khác nhau (độ dài chu trình bằng tổng độ dài các cạnh tạo nên chu trình).

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(3 \le N \le 200\), \(3 \le M \le 2000\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u\), \(v\), \(w\) (\(1 \le u, v \le N\), \(1 \le w \le 10^5\)).

Định dạng đầu ra

• In ra một số nguyên duy nhất là độ dài chu trình ngắn nhất. Nếu không tồn tại chu trình nào, in ra -1.

Ràng buộc

• Subtask 1 (40% số điểm): \(N \le 50\), \(M \le 200\).
• Subtask 2 (60% số điểm): Không có ràng buộc gì thêm.