Có ~N~ thành phố đánh số từ ~1~ đến ~N~, ~N \le 100~. Giữa một số cặp thành phố có đường đi hai chiều nối trực tiếp. Cần chọn một tour du lịch đi qua ít nhất 3 thành phố khác nhau, mỗi thành phố đúng một lần trừ thành phố đầu tiên đi qua đúng hai lần (lần đầu tiên và lần cuối cùng) sao cho tổng chi phí của tour du lịch là ít nhất.

Yêu cầu: Hãy tìm tổng chi phí nhỏ nhất của tour du lịch thỏa mãn điều kiện trên.

Input

• Dòng đầu tiên ghi hai số nguyên ~N, M~ với ~M~ là số đoạn đường nối trực tiếp hai thành phố.
• Tiếp theo là ~M~ dòng, mỗi dòng ghi ba số nguyên dương ~u, v, w~ với ý nghĩa là có đường đi hai chiều trực tiếp từ thành phố ~u~ đến thành phố ~v~ với chi phí ~w~, ~w \le 10000~. Chú ý rằng giữa hai thành phố có thể có nhiều đường nối trực tiếp.

Output

• Một số ~C~ là tổng chi phí của tour được chọn, nếu không có thì ghi số ~0~.

Sample 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

Sample Output 1

61