An mới trúng thầu xây dựng ở thành phố X. Công việc đầu tiên An muốn làm là sửa các con đường trong thành phố. Mạng lưới giao thông ở thành phố X biểu diễn như một tập gồm ~N~ địa điểm được nối bởi ~M~ con đường, con đường thứ ~i~ có chiều dài ~l_i~ mét, chi phí ~c_i~ để sửa chữa và nối hai địa điểm ~u_i, v_i~. Để tạo ra một bản kế hoạch, An phải chọn ra một tập các con đường trong tổng số ~M~ con đường để giữ lại và sửa chữa. Chi phí để sửa đường là tổng chi phí tất cả các con đường trong tập con đó.

An mong muốn giảm tối đa chi phí sửa đường. Tuy nhiên, chính quyền thành phố cũng yêu cầu An giảm thiểu khoảng cách di chuyển giữa các địa điểm và không chấp nhận bất cứ bản kế hoạch nào mà không đáp ứng yêu cầu đó. Cụ thể, với mỗi cặp địa điểm ~(i, j)~ bất kì, nếu tồn tại một đường đi từ ~i~ đến ~j~ có khoảng cách ~l~ mét trên mạng lưới các con đường đã có từ trước, thì trên bản kế hoạch của An cũng có con đường đi qua hai địa điểm đó và có khoảng cách không vượt quá ~l~ mét.

Yêu cầu: Cho mạng lưới giao thông thành phố, em hãy giúp An tìm tập các con đường để giữ lại và sửa chữa với chi phí nhỏ nhất thỏa mãn yêu cầu trên.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ (~1 \le N, M \le 2000~).
• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa 4 số nguyên ~u_i, v_i, l_i~ và ~c_i~ theo nghĩa là tồn tại một con đường nối hai địa điểm ~u_i~ và ~v_i~ có chiều dài ~l_i~ (~0 \le l_i \le 10^9~) và chi phí sửa chữa là ~c_i~ (~1 \le c_i \le 10^9~, ~1 \le u_i, v_i \le N~, ~u_i \neq v_i~).

Output

• Một số nguyên duy nhất là chi phí sửa đường ít nhất đáp ứng yêu cầu.