Vương quốc JOI có \(N\) thành phố, đánh số từ \(1\) đến \(N\), và \(M\) tuyến xe buýt nối giữa các thành phố, đánh số từ \(1\) đến \(M\). Tuyến thứ \(i\) (\(1 \le i \le M\)) đi từ thành phố \(U_i\) đến thành phố \(V_i\), với giá vé \(C_i\) yên. Trên tuyến này, hành khách chỉ được lên xe ở \(U_i\) và chỉ được xuống xe ở \(V_i\). Có thể có nhiều tuyến đi từ cùng một thành phố đến cùng một thành phố khác.

Thế vận hội sắp được tổ chức tại vương quốc JOI. Ngài K là Bộ trưởng Giao thông của vương quốc. Ngay trước Thế vận hội, ngài K sẽ chọn nhiều nhất một tuyến xe buýt và đảo chiều tuyến đó mà không thay đổi giá vé. Cụ thể, nếu chọn tuyến thứ \(i\), trong suốt Thế vận hội tuyến đó sẽ đi từ \(V_i\) đến \(U_i\) thay vì từ \(U_i\) đến \(V_i\). Chi phí đảo chiều là \(D_i\) yên và do ngài K chi trả. Để tránh nhầm lẫn, không được đảo chiều tuyến xe trong thời gian diễn ra Thế vận hội.

Trong Thế vận hội, ngài K sẽ đi xe buýt từ thành phố \(1\) đến thành phố \(N\) rồi quay về thành phố \(1\). Bằng cách chọn một tuyến để đảo chiều, hoặc không đảo chiều tuyến nào, ngài muốn tối thiểu hóa tổng tiền vé của chuyến đi khứ hồi và chi phí đảo chiều.

Cho số thành phố và thông tin các tuyến xe buýt, hãy tính tổng chi phí nhỏ nhất này. Nếu không có lựa chọn hợp lệ nào cho phép thực hiện chuyến đi khứ hồi giữa thành phố \(1\) và thành phố \(N\), hãy in ra \(-1\).

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau. Tất cả giá trị đều là số nguyên.

N M
U_1 V_1 C_1 D_1
...
U_M V_M C_M D_M

Dữ liệu ra

In ra tổng nhỏ nhất của tiền vé đi khứ hồi và chi phí đảo chiều tuyến đã chọn. Nếu không thể thực hiện chuyến đi khứ hồi giữa thành phố \(1\) và thành phố \(N\), in ra \(-1\).

Ràng buộc

• \(2 \le N \le 200\).
• \(1 \le M \le 50\,000\).
• \(1 \le U_i \le N\) với \(1 \le i \le M\).
• \(1 \le V_i \le N\) với \(1 \le i \le M\).
• \(U_i \ne V_i\) với \(1 \le i \le M\).
• \(0 \le C_i \le 1\,000\,000\) với \(1 \le i \le M\).
• \(0 \le D_i \le 1\,000\,000\,000\) với \(1 \le i \le M\).

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung. Chỉ nhận được điểm của một nhóm nếu vượt qua tất cả bộ dữ liệu trong nhóm đó.

1. \(5\) điểm: \(M \le 1000\)
2. \(11\) điểm: \(M\) chẵn; \(U_{2i-1}=U_{2i}\), \(V_{2i-1}=V_{2i}\) và \(C_{2i-1}=C_{2i}\) với mọi \(1 \le i \le M/2\)
3. \(21\) điểm: \(C_i=0\) với mọi \(1 \le i \le M\)
4. \(63\) điểm: Không có

Ví dụ

4 5
1 2 4 4
1 3 2 1
4 3 1 2
4 1 6 1
2 4 2 5

10

4 10
1 2 4 4
1 2 4 4
1 3 2 1
1 3 2 1
4 3 1 2
4 3 1 2
4 1 6 1
4 1 6 1
2 4 2 5
2 4 2 5

10

4 4
1 2 0 4
1 3 0 1
4 3 0 2
4 1 0 1

2

4 5
1 2 4 4
1 3 2 4
4 3 1 5
4 1 6 1
2 4 2 5

12

4 5
2 1 4 4
1 3 2 1
4 3 1 2
4 3 6 1
2 4 2 5

-1

Nguồn

Bản dịch tiếng Việt từ đề chính thức bằng tiếng Anh của Ủy ban Olympic Tin học Nhật Bản, vòng chung kết JOI 2019/2020 ngày 9 tháng 2 năm 2020. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.