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

Input

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

Output:

• In ra chi phí phá hủy ít nhất tìm được.

Sample 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

Sample Output

8

Ràng buộc:

•   2 ≤ N ≤ 1000
•   1 ≤ M ≤ 4*10^5
•   1 ≤ X, Y ≤ N
•   1 ≤ D, C ≤ 10^6