Thị trấn IOI có \(N\) giao lộ, đánh số từ \(1\) đến \(N\), và \(M\) con đường, đánh số từ \(1\) đến \(M\). Mỗi con đường nối hai giao lộ khác nhau và có thể đi theo cả hai chiều. Đường thứ \(i\) (\(1 \le i \le M\)) nối giao lộ \(A_i\) với giao lộ \(B_i\). Không có hai con đường khác nhau nối cùng một cặp giao lộ.

Mỗi đường được sơn một màu, biểu diễn bằng một số nguyên từ \(1\) đến \(M\). Hiện tại, màu của đường thứ \(i\) là \(C_i\). Nhiều đường có thể có cùng màu.

Công ty JOI đã phát triển một robot di chuyển giữa các giao lộ của thị trấn IOI. Khi bạn chỉ định một màu, robot đi theo đường có màu đó tới giao lộ kề bên. Tuy nhiên, nếu tại giao lộ hiện tại có từ hai đường mang màu được chỉ định trở lên, robot không thể xác định phải đi đường nào và sẽ dừng lại.

Robot hiện ở giao lộ \(1\). Bạn muốn đưa robot tới giao lộ \(N\) bằng cách chỉ định màu một số lần. Vì các màu hiện tại có thể không cho phép làm điều đó, bạn được sơn lại một số con đường trước khi robot di chuyển. Với chi phí \(P_i\) yên, có thể sơn lại đường thứ \(i\) thành một màu bất kỳ từ \(1\) đến \(M\).

Cho thông tin về các giao lộ và con đường, hãy tìm tổng chi phí nhỏ nhất. Nếu dù sơn lại các đường như thế nào cũng không thể đưa robot tới giao lộ \(N\), hãy in ra \(-1\).

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn:

N M
A_1 B_1 C_1 P_1
...
A_M B_M C_M P_M

Tất cả các giá trị đầu vào đều là số nguyên.

Dữ liệu ra

In ra một dòng chứa tổng chi phí nhỏ nhất. Nếu không thể đưa robot tới giao lộ \(N\) dù sơn lại các đường như thế nào, in ra \(-1\).

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(1 \le M \le 200\,000\).
• \(1 \le A_i < B_i \le N\) với mọi \(1 \le i \le M\).
• \((A_i,B_i) \ne (A_j,B_j)\) với mọi \(1 \le i < j \le M\).
• \(1 \le C_i \le M\) với mọi \(1 \le i \le M\).
• \(1 \le P_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le M\).

Phân nhóm

• Nhóm 1 (34 điểm): \(N \le 1000\), \(M \le 2000\).
• Nhóm 2 (24 điểm): \(P_i=1\) với mọi \(1 \le i \le M\).
• Nhóm 3 (42 điểm): Không có ràng buộc bổ sung.

Ví dụ

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

3

5 2
1 4 1 2
3 5 1 4

-1

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

1

13 21
7 10 4 4
3 6 4 7
8 10 4 5
3 9 2 5
1 4 4 5
2 6 4 2
3 11 2 2
3 8 16 2
8 11 16 1
6 10 4 14
6 8 16 6
9 12 16 5
5 13 4 6
1 12 4 7
2 4 4 18
2 9 4 10
2 12 4 6
10 13 4 28
5 7 2 5
5 11 2 16
7 13 4 20

7

Nguồn

JOI 2020/2021, vòng chung kết quốc gia, ngày 14/02/2021. Đề gốc của Ủy ban Olympic Tin học Nhật Bản: tiếng Anh, tiếng Nhật. Bản dịch theo giấy phép CC BY-SA 4.0.