Anh DoMixi là streamer số 1 của MixiLand — thị trấn có ~N~ giao lộ đánh số từ ~1~ đến ~N~ và ~M~ con đường đánh số từ ~1~ đến ~M~ (ban quản lý rất ghiền đánh số).

Mỗi con đường nối hai giao lộ khác nhau theo cả hai chiều (hai chiều vì anh DoMixi không thích đi một chiều). Con đường thứ ~i~ nối giao lộ ~A_i~ và ~B_i~. Không có hai con đường nào cùng nối một cặp giao lộ — MixiLand không lãng phí vật liệu xây dựng như vậy. Mỗi con đường được sơn một màu stream — một số nguyên từ ~1~ đến ~M~. Hiện tại màu của con đường ~i~ là ~C_i~. Nhiều con đường có thể cùng màu vì ban quản lý mua sơn theo lốc giảm giá.

Anh DoMixi vừa cho ra mắt DoBot — một robot giao đồ ăn thần thánh đang đứng ở giao lộ ~1~. Mỗi khi anh hét một màu vào mic, DoBot sẽ ngó xung quanh, tìm đúng con đường mang màu đó đang kết nối với giao lộ hiện tại rồi đi qua. Nghe có vẻ ổn... cho đến khi:

Nếu có nhiều hơn một con đường cùng màu nối với giao lộ hiện tại của DoBot, nó không biết rẽ hướng nào, lag giữa đường rồi đứng hình luôn.

Nhiệm vụ của bạn là điều khiển DoBot từ giao lộ ~1~ đến giao lộ ~N~ — nơi anh DoMixi đang chờ nhận đơn hàng. Để làm được điều này, bạn có thể đổi màu một số con đường trước khi DoBot xuất phát. Chi phí đổi màu con đường ~i~ là ~P_i~ xu (đổi sang bất kỳ màu nào từ ~1~ đến ~M~, tha hồ chọn).

Hãy tính tổng chi phí đổi màu nhỏ nhất để DoBot có thể đến được giao lộ ~N~. Nếu dù sơn phết kiểu gì DoBot vẫn không đến nơi được, hãy in ~-1~ (và gọi ship bằng tay cho anh DoMixi).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~.

~M~ dòng tiếp theo, dòng thứ ~i~ chứa bốn số nguyên ~A_i~, ~B_i~, ~C_i~, ~P_i~.

Kết quả

In ra một số nguyên duy nhất — tổng chi phí đổi màu nhỏ nhất để DoBot đến được giao lộ ~N~. Nếu không thể, in ~-1~.

Ví dụ

Ví dụ 1

Đầu vào:

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

Đầu ra:

3

Ví dụ 2

Đầu vào:

5 2
1 4 1 2
3 5 1 4

Đầu ra:

-1

Ví dụ 3

Đầu vào:

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

Đầu ra:

1

Giới hạn

• ~2 \le N \le 100.000~
• ~1 \le M \le 200.000~
• ~1 \le A_i < B_i \le N~
• ~(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~
• ~1 \le P_i \le 10^9~

Subtask