Tại một thị trấn nọ có N ngôi nhà, được đánh số từ 1 đến \(N\). Có \(M\) con đường hai chiều, đánh số từ 1 tới \(M\). Mỗi con đường kết nối hai ngôi nhà khác nhau, con đường thứ \(i\) kết nối ngôi nhà \(A_i\) với \(B_i\), giữa hai nhà chỉ có duy nhất một con đường nối chúng. Điều đặc biệt là mỗi con đường đều có một màu sắc nhất định, được miêu tả bằng các số nguyên từ 1 tới \(M\). Ban đầu con đường thứ \(i\) có màu sắc là \(None\)C_i~ và các con đường có thể có màu giống nhau.

Thị trưởng có một con robot có thể đi vòng quanh thị trấn. Khi bạn đọc cho nó màu nào thì nó sẽ đi theo con đường có màu đó để sang ngôi nhà khác. Tuy nhiên, nếu có nhiều hơn một con đường với màu bạn chọn kề với ngôi nhà robot đang đứng, robot sẽ đứng yên.

Robot đang được đặt tại ngôi nhà thứ 1. Nhiệm vụ của bạn là cần đưa robot đến ngôi nhà thứ \(N\) bằng việc đọc màu cho nó. Tuy nhiên, nó không thể lúc nào cũng đi được, bạn cần phải thay đổi màu của một số con đường để thuận lợi cho việc di chuyển. Chi phí để đổi màu cho con đường thứ \(i\) là \(P_i\) đồng, các màu sau khi đổi vẫn phải đảm bảo là các số nguyên từ 1 tới \(M\).

Yêu cầu: Tính tổng chi phí đổi màu ít nhất để robot có thể di chuyển từ nhà thứ 1 đến nhà thứ \(N\). Nếu không có phương án nào, hãy in ra \(-1\).

Dữ liệu vào:

• Dòng 1:chứa hai số nguyên \(N, M (2≤N≤10^5;1≤M≤2*10^5 ).\)

• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa 4 số nguyên dương \(A_i, B_i, C_i, P_i (1≤A_i<B_i≤N,1≤C_i≤M,1≤P_i≤10^9).\)

Kết quả:

• In ra chi phí đổi màu ít nhất để robot có thể di chuyển từ ngôi nhà thứ 1 đến ngôi nhà thứ \(N\). Nếu không có phương án nào, hãy in ra \(-1\).

Ràng buộc:

• Subtask 1: 30% số test ứng với 30% số điểm của bài có: \(N≤1000, M≤2000.\)

• Subtask 2: 30% số test ứng với 30% số điểm của bài có: \(P_i=1 (1≤i≤M).\)

• Subtask 3: 40% số test ứng với 40% số điểm của bài có: Không có ràng buộc gì thêm.

Sample Input

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

Sample Output

3

Giải thích

• Bạn có thể đổi màu con đường cuối cùng từ màu 4 sang màu 2, mất 2 đồng. Sau đó đổi màu con đường thứ 4, từ màu 3 sang màu 4, mất 1 đồng. Tổng chi phí là 3 đồng.

• Sau khi đổi màu, đầu tiên bạn đọc màu 2, robot sẽ di chuyển từ ngôi nhà 1 sang ngôi nhà thứ 2. Sau đó bạn đọc màu 4, robot sẽ di chuyển tiếp sang ngôi nhà thứ 4. Có thể thấy 3 đồng là chi phí tối ưu nhất cho trường hợp này.