Bản đồ một khu du lịch gồm địa điểm và đường đi hai chiều. Giữa hai địa điểm có thể có nhiều đường đi nối trực tiếp giữa chúng. Một khách du lịch lữ hành muốn đi bộ từ địa điểm tới địa điểm rồi quay trở lại địa điểm bằng một hành trình thỏa mãn các yêu cầu sau:
Chỉ đi trên các đường đi trong đường đã cho;
Không có đường đi nào qua nhiều hơn một lần trong hành trình;
Độ dài hành trình (tính bằng tổng độ dài các đường đi trên hành trình) là nhỏ nhất có thể.
Hãy chỉ ra một hành trình thỏa mãn các yêu cầu trên hoặc cho biết rằng yêu cầu của du khách là không thể thực hiện được
Dữ liệu vào:
Dòng đầu chứa hai số nguyên dương ;
dòng tiếp theo, dòng thứ chứa ba số nguyên dương tương ứng với một đường đi nối địa điểm với địa điểm và độ dài đường đi đó là . Độ dài đường đi được đo bằng micro mét , không có đường đi nào dài hơn .
Dữ liệu ra:
Dòng đầu ghi độ dài hành trình, trong trường hợp không tồn tại hành trình thỏa mãn các yêu cầu đặt ra thì dòng này ghi số .
Nếu tồn tại hành trình, dòng thứ hai ghi các địa điểm theo đúng thứ tự trên hành trình tìm được, bắt đầu và kết thúc ở địa điểm .
