Tại thành phố Tương lai có ~N~ trạm, đượ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 trạm khác nhau, con đường thứ ~i~ kết nối trạm ~A_i~ với ~B_i~, giữa hai trạm 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~ nhưng có thể nhiều con đường có cùng màu.

Chủ tịch thành phố sở hữu một robot thông minh có thể đi vòng quanh thành phố. Khi bạn đọc cho nó màu nào thì nó sẽ đi theo con đường có màu đó để sang trạm 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 trạm robot đang đứng, robot sẽ đứng yên.

Robot xuất phát tại trạm thứ ~1~. Nhiệm vụ của bạn là chỉ dẫn robot đến trạm 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ìm tổng chi phí đổi màu ít nhất để robot có thể di chuyển từ trạm thứ ~1~ đến trạm thứ ~N~. Nếu không có phương án nào, hãy in ra ~-1~.

Input

• Dòng ~1~: ~N~, ~M~ lần lượt là số trạm, số con đường trong thành phố ~(2 \le N \le 100000, 1 \le M \le 200000)~.

• ~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~ với:

  • ~1 \le A_i < B_i \le N~;

  • ~1 \le C_i \le M~;

  • ~1 \le P_i \le 1000000000~.

Output

Gồm một số nguyên duy nhất là chi phí đổi màu ít nhất để robot có thể di chuyển từ trạm thứ ~1~ đến trạm thứ ~N~. Nếu không có phương án nào, hãy in ra ~-1~.

Scoring

Sample Input 1

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 1

3

Notes

• Đổi màu cạnh ~(1, 2)~ từ màu ~4~ thành màu ~1~, chi phí ~2~.

• Đổi màu cạnh ~(2, 4)~ từ màu ~3~ thành màu ~2~, chi phí ~1~.

• Robot đi ~1 \rightarrow 2 \rightarrow 4~. Tổng chi phí đổi màu: ~2 + 1 = 3~.