Link tải test: tại đây

Ở nước Alpha có 𝑛 thành phố đánh số từ 1 tới 𝑛 và 𝑚 con đường đất nối chúng với nhau đánh số từ 1 tới 𝑚. Con đường thứ 𝑖 từ thành phố 𝑢_𝑖 tới thành phố 𝑣_𝑖 và cho phép đi lại giữa hai thành phố đó theo cả hai chiều. Hạ tầng giao thông cần được nâng cấp nhưng do ngân sách nhà nước còn eo hẹp, chính phủ muốn chọn ra 𝑛 −1 con đường để rải nhựa sao cho với hai thành phố bất kỳ luôn tồn tại một tuyến đường qua các con đường rải nhựa nối chúng với nhau và giá trung bình 1 km đường là rẻ nhất. Biết rằng con đường thứ 𝑖 có độ dài 𝑙_𝑖 km và để rải nhựa con đường đó tốn chi phí là 𝑐_𝑖. Hệ thống các con đường đảm bảo sự đi lại giữa hai thành phố bất kỳ. Giá trung bình của 1 km đường trong một phương án rải nhựa được tính bằng:

Tổng chi phí rải nhựa các con đường trong phương án

Tổng độ dài các con đường được rải nhựa trong phương án

Yêu cầu: Hãy xác định phương án tối ưu để rải nhựa các con đường theo yêu cầu của chính phủ.

Dữ liệu:

• Dòng 1: Chứa hai số nguyên dương 𝑛, 𝑚 ≤ 10⁴;

• 𝑚 dòng tiếp theo, dòng thứ 𝑖 chứa 4 số nguyên dương 𝑢_𝑖, 𝑣_𝑖, 𝑙_𝑖, 𝑐_𝑖 (1 ≤ 𝑙_𝑖, 𝑐_𝑖 ≤ 10⁵).

Kết quả: Ghi ra 𝑛−1 số nguyên trên một dòng là số hiệu các con đường trong phương án tối ưu tìm được.

Ví dụ:

Ràng buộc:

• Có 50% số test có 𝑛, 𝑚, 𝑙, 𝑐 ≤ 100;

• 50% số test còn lại không có ràng buộc gì thêm.