Có N thành phố đánh số từ 1 đến N, N<=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.

Dữ liệu: vào từ file DULICH.INP gồm:

- 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<=10000. Chú ý rằng giữa hai thành phố có thể có nhiều đường nối trực tiếp.

Kết quả: ghi ra file văn bản DULICH.OUT một số C là tổng chi phí của tour được chọn, nếu không có thì ghi số 0.

Ví dụ: