Ở đất nước nọ có ~n~ thành phố đánh số từ 1 tới ~n~ và ~m~ con đường đất nối chúng với nhau đánh số từ 1 tới ~m~. Con đường thứ ~i~ từ thành phố ~u_i~ tới thành phố ~v_i~ 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, nhà vua muốn chọn ra ~n - 1~ con đường để lát đá 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 lát đá 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ứ ~i~ có độ dài ~l_i~ km và để lát đá con đường đó tốn chi phí là ~c_i~. 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 lát đá được tính bằng: ~ \frac{\text{Tổng chi phí lát đá các con đường trong phương án}}{\text{Tổng độ dài các con đường được lát đá trong phương án}} ~

Yêu cầu: Hãy xác định phương án tối ưu để lát đá các con đường theo yêu cầu của nhà vua.

Input

• Dòng 1: Chứa hai số nguyên dương ~n, m \le 10^4~.
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa 4 số nguyên dương ~u_i, v_i, l_i, c_i~ (~1 \le l_i, c_i \le 10^5~).

Output

• ~n - 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.

Sample Input 1

4 4 
1 2 12 1 
4 3 12 1 
2 3 3 2 
2 4 24 14

Sample Output 1

1 2 3