Busy Beaver đang khám phá khuôn viên ngầm của MIT. Có $N$ tòa nhà được đánh số từ $1, \dots, N$ và $M$ đường hầm được đánh số từ $1, \dots, M$ kết nối các cặp tòa nhà nhất định. Đường hầm thứ $i$ kết nối tòa nhà $a_i$ và $b_i$. Để đi vào đường hầm, trước tiên bạn phải trả $c_i$ đồng xu. Tuy nhiên, sau khi đi qua đường hầm và thưởng thức nghệ thuật bên trong, bạn sẽ được thưởng $r_i$ đồng xu.
Busy Beaver sống ở tòa nhà $1$ và sẽ tham dự bài giảng của mình tại tòa nhà $N$. Số lượng đồng xu tối thiểu mà cậu ấy cần mang theo để có thể đến được tòa nhà $N$ là bao nhiêu?
Hãy lưu ý những điều sau:
- Các đường hầm có thể được đi qua theo bất kỳ hướng nào, bất kỳ số lần nào. Mỗi lần đi qua, phí sẽ được tính và phần thưởng sẽ được nhận.
- Busy Beaver có thể sử dụng số đồng xu được thưởng để trả phí vào cửa cho các lần sau.
- Có thể có nhiều hơn một đường hầm kết nối hai tòa nhà.
- Bạn không bao giờ được phép có số đồng xu âm.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách, $N$ và $M$ ($2\le N \le 10^5$, $1\le M \le 2\cdot 10^5$).
$M$ dòng tiếp theo mô tả các đường hầm. Dòng thứ $i$ gồm bốn số nguyên cách nhau bởi dấu cách: $a_i$, $b_i$, $c_i$, và $r_i$ ($1 \le a_i,b_i \le N$, $a_i \ne b_i$, $0 \le c_i,r_i \le 10^9$).
Đảm bảo rằng tòa nhà $N$ có thể đến được từ tòa nhà $1$ khi bắt đầu với một số lượng đồng xu hữu hạn.
Dữ liệu ra
In ra một dòng duy nhất chứa kết quả.
Nhiệm vụ con
- ($20$ điểm) Có $N-1$ đường hầm: một đường hầm kết nối tòa nhà $i$ với tòa nhà $i+1$ cho mọi $1 \le i < N$.
- ($20$ điểm) $r_i = 0$ cho mọi $1 \le i \le M$.
- ($20$ điểm) $c_i = r_i$ cho mọi $1 \le i \le M$.
- ($20$ điểm) $c_i \ge r_i$ cho mọi $1 \le i \le M$.
- ($20$ điểm) Không có ràng buộc bổ sung.
Ví dụ
Ví dụ 1
3 3 1 2 2 1 2 3 3 0 1 3 5 0
Kết quả 1
4
Ví dụ 2
4 3 1 2 3 1 2 3 1 2 3 4 2 4
Kết quả 2
3
Ví dụ 3
3 4 1 2 4 3 1 2 4 6 2 1 5 4 2 3 10 9
Kết quả 3
4
Ghi chú
Giải thích ví dụ 1
Nếu Busy Beaver bắt đầu với $4$ đồng xu, cậu ấy có thể đi qua đường hầm từ tòa nhà $1$ đến tòa nhà $2$, trả $2$ đồng xu và nhận lại $1$ đồng xu (vậy cậu ấy có $4-2+1=3$ đồng xu khi đến tòa nhà $2$), sau đó đi qua đường hầm từ tòa nhà $2$ đến tòa nhà $3$ bằng $3$ đồng xu của mình.
Giải thích ví dụ 2
Nếu Busy Beaver bắt đầu với $3$ đồng xu, cậu ấy có thể đi qua đường hầm từ tòa nhà $1$ đến tòa nhà $2$, còn lại $1$ đồng xu khi đến nơi. Sau đó, cậu ấy có thể đi đến tòa nhà $3$, sau đó cậu ấy có $2$ đồng xu. Cuối cùng, cậu ấy có thể đến tòa nhà $4$ bằng cách trả $2$ đồng xu và nhận được $4$ đồng xu khi đến nơi.
Giải thích ví dụ 3
Busy Beaver có thể bắt đầu ở tòa nhà $1$ với $4$ đồng xu, đi qua đường hầm $2$ ba lần, vào đường hầm $4$ với $10$ đồng xu và đến tòa nhà $3$ với $9$ đồng xu. Có thể chứng minh rằng Busy Beaver không thể đến được tòa nhà $3$ nếu bắt đầu với ít hơn $4$ đồng xu.