MegaChip IV Tuyệt vời, vua của nước Baitotxia, muốn gả chồng cho công chúa Ađa. Công chúa muốn người chồng tương lai phải thông minh, không bủn xỉn nhưng cũng không hoang phí. Sau thời gian dài suy nghĩ, đức vua quyết định xây một cung điện gồm phòng đánh số từ đến và có hành lang hai chiều nối trực tiếp một số cặp phòng, phòng số là phòng vào, phòng số là phòng của công chúa.
Mỗi chàng trai được phát đồng và phải chọn một hành trình qua một dãy các phòng (không nhất thiết là khác nhau) bắt đầu từ phòng vào, kết thúc ở phòng công chúa. Mỗi lần đến một phòng trên hành trình, cần phải trả một số tiền qui định đối với phòng đó. Chàng trai nào chọn được một hành trình mà khi đến phòng công chúa thì tiêu hết đúng đồng sẽ được làm phò mã.
Đã nhiều năm trôi qua, chưa có chàng trai nào trở thành phò mã và công chúa Ađa vẫn còn đang chờ đợi người chồng lý tưởng của mình. Liệu bạn có thể giúp một bạn trai thân thiết đang sống tại Baitotxia không?.
Dữ liệu vào:
Dòng đầu tiên ghi số nguyên dương ;
Dòng thứ hai ghi số nguyên dương , là số tiền phải trả khi đến phòng thứ ;
dòng tiếp theo, mỗi dòng ghi hai số nguyên dương , là hai phòng đầu mút của một hành lang.
Dữ liệu ra:
Một dòng viết dãy các phòng theo trình tự từ phòng đầu đến phòng công chúa.
