Farmer John vừa mua một chiếc ô tô mới trên mạng. Vì quá vội, khi chọn các tính năng bổ sung cho xe, ông vô tình nhấn nút "Submit" hai lần; kết quả là chiếc xe được trang bị tới hai hệ thống định vị GPS! Tệ hơn nữa, hai hệ thống này thường đưa ra những quyết định trái ngược nhau về lộ trình Farmer John nên đi.

Bản đồ khu vực Farmer John sinh sống gồm \(N\) giao lộ (\(2 \le N \le 10\,000\)) và \(M\) con đường có hướng (\(1 \le M \le 50\,000\)). Đường thứ \(i\) nối từ giao lộ \(A_i\) (\(1 \le A_i \le N\)) đến giao lộ \(B_i\) (\(1 \le B_i \le N\)). Có thể có nhiều con đường nối cùng một cặp giao lộ. Một con đường hai chiều được biểu diễn bằng hai con đường có hướng riêng biệt theo hai hướng ngược nhau. Nhà của Farmer John nằm tại giao lộ \(1\), còn trang trại của ông nằm tại giao lộ \(N\). Bảo đảm có thể đi từ nhà đến trang trại theo một dãy các con đường có hướng.

Cả hai thiết bị GPS đều dùng cùng bản đồ nói trên, nhưng chúng đánh giá thời gian đi trên mỗi con đường khác nhau. Theo thiết bị GPS thứ nhất, cần \(P_i\) đơn vị thời gian để đi qua đường thứ \(i\); theo thiết bị thứ hai, cần \(Q_i\) đơn vị thời gian. Mỗi thời gian là một số nguyên trong đoạn từ \(1\) đến \(100\,000\).

Farmer John muốn đi từ nhà đến trang trại. Tuy nhiên, mỗi thiết bị GPS sẽ lớn tiếng phàn nàn bất cứ khi nào ông đi theo một con đường, chẳng hạn từ giao lộ \(X\) đến giao lộ \(Y\), mà thiết bị đó cho rằng không thuộc một đường đi ngắn nhất từ \(X\) đến trang trại. Cả hai thiết bị đều có thể cùng phàn nàn nếu Farmer John đi trên một con đường mà không thiết bị nào thích.

Hãy giúp Farmer John xác định tổng số lời phàn nàn nhỏ nhất có thể nhận được nếu ông chọn lộ trình thích hợp. Nếu cả hai thiết bị cùng phàn nàn khi ông đi qua một con đường, tổng số lời phàn nàn tăng thêm \(2\).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\).
• \(M\) dòng tiếp theo, dòng mô tả đường thứ \(i\) chứa bốn số nguyên \(A_i\), \(B_i\), \(P_i\), \(Q_i\).

Ràng buộc

• \(2 \le N \le 10\,000\).
• \(1 \le M \le 50\,000\).
• \(1 \le A_i,B_i \le N\).
• \(1 \le P_i,Q_i \le 100\,000\).
• Có thể có nhiều con đường nối cùng một cặp giao lộ; đường hai chiều được biểu diễn bằng hai đường có hướng ngược nhau.
• Bảo đảm có đường đi từ giao lộ \(1\) đến giao lộ \(N\).

Dữ liệu ra

• In ra tổng số lời phàn nàn nhỏ nhất Farmer John có thể nhận được nếu chọn tối ưu lộ trình từ nhà đến trang trại.

Ví dụ

5 7
3 4 7 1
1 3 2 20
1 4 17 18
4 5 25 3
1 2 10 1
3 5 4 14
2 4 6 5

1

Nguồn

USACO 2014 US Open, Silver — Problem 2: Dueling GPSs

Tác giả đề: Brian Dean, 2014.