B. TSP - Bài toán người du lịch

Một người du lịch xuất phát từ thành phố thứ nhất muốn đi thăm quan tất cả thành phố khác, mỗi thành phố đúng một lần, rồi quay trở lại thành phố xuất phát.

Yêu cầu: Cho biết chi phí đi lại giữa các thành phố, hãy giúp người du lịch tìm hành trình với tổng chi phí là nhỏ nhất.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên dương cách nhau bởi dấu cách ;
• dòng tiếp theo mỗi dòng chứa ba số nguyên dương biểu thị chi phí đi trực tiếp từ thành phố đến thành phố là .

Lưu ý: Nếu từ thành phố đến thành phố nào không mô tả chi phí đi lại thì có nghĩa là không có đường đi trực tiếp từ đến .

Dữ liệu ra:

• Ghi ra duy nhất một số là tổng chi phí hành trình nhỏ nhất tìm được.

Ví dụ

Dữ liệu vào:

2 2
1 2 3
2 1 2

Dữ liệu ra:

5