Cho đồ thị vô hướng liên thông có trọng số không âm gồm \(N\) đỉnh và \(M\) cạnh. Hãy tìm tổng trọng số nhỏ nhất của một chu trình bắt đầu từ địa điểm 1 đi qua tất cả các cạnh ít nhất một lần rồi quay về 1.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) (\(2 \le N \le 100\), \(1 \le M \le 2000\)). Đồ thị đảm bảo số lượng đỉnh có bậc lẻ không vượt quá 16.
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v\) và \(w\) (\(1 \le u, v \le N\), \(0 \le w \le 1000\)) mô tả một con đường hai chiều nối giữa \(u\) và \(v\) có trọng số \(w\).

Kết quả ra

• In ra một số nguyên duy nhất là tổng trọng số nhỏ nhất tìm được.

Ví dụ

Input

4 4
1 2 10
2 3 20
3 4 30
4 1 40

Output

100