G. TUNNEL - Các đường hầm

Sau chuyến đi công du dài ngày, Giáo sư X lại càng thấy cần phải góp công sức để thay đổi chất lượng cuộc sống tại thị trấn nơi ông đang ở. Việc đầu tiên mà ông dự định làm là gửi bản kiến nghị về việc xây dựng mô hình giao thông mới dành cho các phương tiện giao thông công cộng nhằm tránh tắc đường, khói bụi và ô nhiễm: đó là hệ thống giao thông dưới lòng đất. Để thuyết phục được người nghe, ông xây dựng một mô hình. Trên mô hình này, ông đặt điểm dừng đỗ cho các phương tiện đi lại (được đánh số từ đến ). Việc đi lại giữa các điểm này hoàn toàn bằng các tuyến đường hầm. Có con đường hai chiều nối giữa điểm đó, mỗi con đường gồm hai thông tin: độ dài tuyến đường và chiều cao tối đa của phương tiện có thể đi qua được. Một vài điểm dừng đỗ có thể không có đường nối trực tiếp.

Trước buổi thuyết trình, Giáo sư nhận được câu hỏi: với hai điểm dừng đỗ và cho trước, hãy chỉ ra một cách đi từ điểm đến điểm sao cho độ cao của phương tiện giao thông đi qua các tuyến đường theo cách đi đó là lớn nhất có thể. Nếu có nhiều cách đi, hãy chỉ cách đi có tổng chiều dài nhỏ nhất. Vì câu hỏi này quá dễ nên ông giao cho các học trò của mình trả lời, còn ông sẽ chỉ tập trung vào buổi thuyết trình.

Dữ liệu vào:

• Dòng đầu ghi số ;
• dòng tiếp, mỗi dòng mô tả một đường nối hai điểm gồm số : với ý nghĩa đường đi từ đến có độ cao tối đa là và chiều dài là .

Dữ liệu ra:

• Dòng đầu ghi số là số điểm dừng đỗ phải đi qua (kể cả và );
• Dòng sau là số lần lượt là số hiệu các điểm dừng đỗ tương ứng theo thứ tự trên đường đi, bắt đầu là và kết thúc là .

Ví dụ:

Dữ liệu vào:

6 10 2 4
2 1 9 1
5 2 4 7
1 5 2 6
6 3 2 2
4 5 1 1
2 6 3 4
1 6 5 2
6 5 2 3
3 4 2 3
3 5 3 1

Dữ liệu ra:

5
2 1 6 3 4