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ả: CEDGEDES.OUT

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

Ví dụ:

Input	Output	Minh họa
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	8

Giải thích:

Nhìn vào hình ta thấy đường đi ngắn nhất từ 1 🡪 4 là 2. Khi ta xóa cạnh (1,4) thì đường đi ngắn nhất sẽ tăng lên là 9 (1 – 2 – 4).

🡺 Chi phí phá hủy là 8

Ràng buộc:

+ 2 ≤ N ≤ 1000

+ 1 ≤ M ≤ 4*10⁵

+ 1 ≤ X, Y ≤ N

+ 1 ≤ D, C ≤ 10⁶