Cho một đồ thị G có ~n~ đỉnh và ~m~ cạnh nối 2 chiều. Mỗi cạnh có một độ dài và một chi phí phá hủy. Bạn hãy tăng độ dài đường đi ngắn nhất từ đỉnh 1 đến đỉnh ~n~ bằng cách phá hủy một số cạnh nối.

Yêu cầu: Hãy tìm cách phá hủy sao cho chi phí phá hủy ít nhất

Dữ liệu vào:

• Dòng 1: Ghi 2 số nguyên ~n,m ~
• ~m~ dòng tiếp theo: Mỗi dòng ghi 4 số nguyên ~x,y,d,c~ cho biết có cạnh nối giữa đỉnh ~x~ và đỉnh ~y~. Cạnh nối có độ dài d và chi phí phá hủy là ~c~.

Kết quả: + In ra chi phí phá hủy ít nhất tìm được.

Ràng buộc

• ~2 ≤ n ≤ 1000~
• ~1 ≤ m ≤ 4.10^5~
• ~1 ≤ x, y ≤ n~
• ~1 ≤ d, c ≤ 10^6~

Ví dụ:

Input

4 6
1 2 4 1
1 3 8 6
1 4 2 8
2 3 8 8
2 4 5 7
3 4 7 5 

Output

8