Tại một thị trấn nọ có \(𝑁\) 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ứ \(𝑖\) kết nối ngôi nhà \(𝐴_𝑖\) vớ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à \(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.

Ban đầu Robot đượ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ứ \(𝑁\) 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: Bạn hãy viết một chương trình tìm tổng 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ếu không có phương án nào, hãy in ra \(−1\).

Input

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

• \(𝑀\) dòng tiếp theo, dòng thứ \(𝑖\) chứa 4 số nguyên dương \(A_i, B_i, C_i, P_i . (1 ≤ 𝐴_𝑖 < 𝐵_𝑖 ≤ 𝑁 , 1 ≤ 𝐶_𝑖 ≤ 𝑀, 1 ≤ P-i ≤ 10^9). \)

Output

• 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ếu không có phương án nào, hãy in ra \(−1\).

Ràng buộc:

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

• 25% số test ứng với 25% số điểm của bài có: \(P_i = 1\)

• 35% số test ứng với 35% 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

Sample Input

5 2
1 4 1 2
3 5 1 4

Sample Output

-1