Để chào mừng đội tuyển đến Đà Lạt học, BTC quyết định tổ chức một chuyến du lịch tham quan Đà Lạt cho các đội. Do việc tổ chức một chuyến du lịch không phải là đơn giản, Dũng được giao ~ X ~ đồng để vạch sẵn lộ trình tham quan và đặt Grap cho các thành viên. Dũng quyết định lộ trình anh vạch ra sẽ xuất phát tại một điểm du lịch, đi qua một số điểm du lịch khác một lần và quay lại điểm xuất phát. Do anh bận nhiều công việc, cộng với việc anh muốn tiết kiệm nhiều tiền cho nhóm nhất có thể, anh muốn lộ trình mình vạch ra phải ngắn nhất có thể (nhưng cũng không được ngắn quá để tránh bị nghi ngờ). Anh quyết định viết một chương trình để giải bài toán trên. Thành phố Đà Lạt có ~ n ~ địa điểm du lịch được đánh số từ 1 đến ~ n ~ và ~ m ~ con đường hai chiều nối giữa các điểm du lịch đó. Hai điểm du lịch có thể được nối với nhau bằng nhiều con đường, nhưng một con đường không thể nối một điểm du lịch với nhau. Một lộ trình có thể được mô tả bằng một dãy các con đường ~ y_1, y_2,…, y_k ~ ~ (k>2) ~. Con đường ~ y_i ~ ~ (1 ≤ i ≤ k-1) ~ nối giữa hai điểm du lịch ~ x_i ~ và ~ x_{i+1} ~, riêng con đường ~ y_k ~ nối giữa điểm du lịch ~ x_k ~ và ~ x_1 ~. Các số ~ x_1, x_2,…,x_k ~ đôi một khác nhau. Độ dài của lộ trình là tổng độ dài các con đường trong lộ trình, hay bằng ~ L{y_1}+L{y_2}+⋯+L{y_k} ~ với ~ L{y_i} ~ là độ dài đường ~ y_i ~ ~ (1 ≤ i ≤ k) ~. Nhiệm vụ của bạn là viết chương trình tìm độ dài của lộ trình ngắn nhất từ những thông tin trên (để từ đó anh có thể kiểm tra chương trình của mình).

Dữ liệu vào

Gồm 1 đến 5 bộ dữ liệu, mỗi bộ có cấu trúc như sau: + Dòng đầu tiên chứa số nguyên dương ~ n ~ và ~ m ~ lần lượt là số điểm du lịch và số con đường nối giữa các điểm du lịch ở Đà Lạt ~ (1 ≤ n ≤ 100; 3 ≤ m ≤ n*(n-1) ) ~. + ~ m ~ dòng tiếp theo, mỗi dòng gồm ba số nguyên ~ a, b, l ~ mô tả một con đường hai chiều nối từ điểm du lịch ~ a ~ đến điểm du lịch ~ b ~ và có độ dài ~ l ~ ~ ( 1 ≤ a, b ≤ n; a ≠ b; 1 ≤ l ≤ 300) ~. Dữ liệu kết thúc bằng một dòng chứa số ~ -1 ~.

Kết quả

Với mỗi bộ dữ liệu, in ra một dòng chứa kết quả của bộ dữ liệu đó. Nếu không có lộ trình nào thích hợp thỏa mãn các điều kiện trên, in ra ~ -1 ~. Nếu tồn tại lộ trình có độ dài ngắn nhất, in ra một số nguyên là độ dài của lộ trình ngắn nhất đó.

Ràng buộc

Ví dụ:

Input 1

5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20
4 3
1 2 10
1 3 20
1 4 30
-1 

Output 1

61
-1