Cảnh sát Byteland nhận được thông báo nặc danh cho biết trùm mafia địa phương sẽ chuyển một món hàng lớn từ cảng tới nhà kho bí mật trong nước. Cảnh sát cũng biết được ngày vận chuyển và việc vận chuyển được thực hiện bằng ô tô trên mạng đường cao tốc quốc gia.
Mạng đường cao tốc bao gồm các đoạn đường hai chiều, mỗi đoạn đường nối hai trạm thu phí khác nhau. Mỗi trạm thu phí có thể nối với nhiều trạm khác. Xe chỉ có thể vào hoặc ra khỏi đường cao tốc tại các trạm thu phí. Mỗi trạm thu phí có một mức lệ phí riêng. Biết rằng xe của bọn mafia sẽ vào đường cao tốc ở trạm thu phí gần cảng nhất và ra khỏi đường cao tốc ở trạm thu phí gần nhà kho nhất. Cảnh sát đặc nhiệm sẽ bố trí chốt lực lượng ở một số trạm để đón lõng bọn tội phạm. Đó là những trạm mà xe của chúng sẽ phải đi qua dù tới nhà kho bằng con đường nào, ngoài ra, tổng chi phí mua vé ở các trạm này phải là nhỏ nhất. Ở ví dụ nêu trên sơ đồ, các điểm chốt là trạm và trạm với tổng chi phí là .
Yêu cầu: Cho là số trạm thu phí, là số đoạn đường trong mạng giao thông, trạm gần cảng nhất và trạm gần kho nhất, chi phí ở trạm , các đoạn đường được mô tả dưới dạng cặp số nguyên – các trạm thu phí ở hai đầu. Hãy chỉ ra các trạm cần bố trí chốt chặn. Giả thiết luôn tồn tại đường đi từ tới .
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên và ;
Dòng thứ hai chứa hai số nguyên và ;
Dòng thứ trong dòng tiếp theo chứa số nguyên ;
Dòng thứ trong dòng tiếp theo chứa số nguyên ; mỗi đoạn đường chỉ mô tả một lần.
Kết quả:
Đưa ra trên một dòng danh sách các điểm cần chốt chặn, hai số liên tiếp được ghi cách nhau một khoảng trắng.
