Ràng buộc

• ~2 \le N \le 1000~;
• ~1 \le M \le 4\times 10^5~;
• ~1 \le X, Y \le N~;
• ~1 \le D, C \le 10^6~.

Sample Input 1

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 1

8

Giải thích

Nhìn vào hình ta thấy đường đi ngắn nhất từ ~1\rightarrow 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 \rightarrow 2 \rightarrow 4)~. Chi phí phá hủy là ~8~.