Centre for Gifted Education - Hanoi university of Technology

Bài toán Người du lịch (Travelling Salesman Problem)

Tỷ phú Zone là 1 trong những doanh nhân thành công nhất thế giới, bây giờ ông đã già, với số tiền khổng lồ có trong tay, Zone làm các công tác từ thiện ở nhiều nước trên thế giới. Zone sẽ phát triển quỹ từ thiện của mình ở N nước trên thế giới, ông muốn nhân dịp này có luôn 1 chuyến du lịch vòng quang thế giới.

Zone đang ở nước thứ nhất, ông ta muốn tìm 1 hành trình đi qua tất cả các nước còn lại, mỗi nước đúng 1 lần. Tuy giàu có nhưng Zone muốn tiết kiệm chi phí du lịch của mình thông qua các chuyến bay để ông ta có đủ số tiền lớn hơn làm từ thiện. Bạn hãy tìm 1 hành trình tối ưu cho Zone.

Zone đã có danh sách các chuyến bay liên thông giữa các nước và giá vé cho từng chuyến bay. Tuy nhiên có 1 số nước Zone muốn trực tiếp từ nước này sang nước kia vì lý do bất ổn chính trị của 2 nước này.

Input

Dòng 1: ghi 2 số nguyên n, m (n là số nước, m là số chuyến bay trực tiếp giữa 2 nước).

M dòng tiếp theo: Mỗi dòng ghi 3 số i, j, C với ý nghĩa có chuyến bay từ i đến j và ngược lại với giá vé là $ C.

Output

Dòng 1: Ghi tổng chi phí chành trình.

Dòng 2: Ghi số hiệu các nước lần lượt trên hành trình của Zone.

Example

Input:
4 8
1 2 1
2 5 1
5 3 2
3 4 1
1 5 10
5 4 6
2 4 4
3 1 7

Output:
4
1 2 5 3 4

Giới hạn:
1 <= n <= 100
1 <= C <= 108

Chỉ dẫn lịch sử:

Bài toán người du lịch được phát biểu vào thế kỷ 17 bởi hai nhà toán học vương quốc Anh là Sir William Rowan Hamilton và Thomas Penyngton Kirkman, và được ghi trong cuốn giáo trình Lý thuyết đồ thị nổi tiếng của Oxford. Nó nhanh chóng trở thành bài toán khó thách thức toàn thế giới bởi độ phức tạp thuật toán tăng theo hàm số mũ (trong chuyên ngành thuật toán người ta còn gọi chúng là những bài toán NP-hard). Người ta bắt đầu thử và công bố các kết quả giải bài toán này trên máy tính từ năm 1954 (49 đỉnh), cho đến năm 2004 bài toán giải được với số đỉnh lên tới 24.978, và dự báo sẽ còn tiếp tục tăng cao nữa.