Cuộc thi lập trình điều khiển robot do thành phố H đăng cai được tổ chức hằng năm. Năm nay, các đội tham gia dự thi phải thiết kế một chiếc ô tô tự động sử dụng cảm biến màu sắc để di chuyển trên một sa hình điện tử cho trước. Sa hình gồm ~n~ trạm và ~m~ con đường nối hai chiều. Các trạm được đánh số thứ tự từ ~1~ đến ~n~. Các con đường được đánh số thứ tự từ ~1~ đến ~m~ và ban đầu có màu ~c_i~ ~(1 \le i \le m)~. Giữa hai trạm chỉ có duy nhất một con đường.

Ô tô xuất phát từ trạm ~1~ và di chuyển đến trạm ~n~. Tại mỗi trạm, ô tô sẽ chọn một màu và di chuyển theo con đường có màu đó để tới trạm kế tiếp. Tuy nhiên, ô tô sẽ dừng lại khi có nhiều hơn một con đường kề với trạm ô tô đang đứng mà cùng màu với màu đã chọn. Ban tổ chức cho phép các đội thay đổi màu của một số con đường để xử lý tình huống này. Chi phí để đổi màu con đường thứ ~i~ ~(1 \le i \le m)~ là ~a_i~. Các màu sau khi đổi vẫn đảm bảo là một số nguyên từ ~1~ đến ~m~.

Yêu cầu: Xác định chi phí đổi màu ít nhất để ô tô có thể di chuyển từ trạm ~1~ đến trạm ~n~. Nếu không có cách di chuyển nào thì in ra ~-1~.

Input

• Dòng đầu tiên chứa hai số nguyên ~n, m~ ~(2 \le n \le 10^5, 1 \le m \le 2 \cdot 10^5)~ lần lượt là số trạm và số con đường trên sa hình;

• ~m~ dòng tiếp theo, dòng thứ ~i~ ~(1 \le i \le m)~ gồm bốn số nguyên dương ~u_i, v_i, c_i, a_i~ ~(1 \le u_i < v_i \le n, 1 \le c_i \le m, 1 \le a_i \le 10^9)~ mô tả con đường nối hai trạm ~u_i, v_i~ có màu ~c_i~ và chi phí đổi màu là ~a_i~.

Output

Ghi ra một số nguyên duy nhất là chi phí đổi màu ít nhất. Nếu không có cách di chuyển nào thì in ra ~-1~.

Scoring

Sample Input 1

4 6
1 2 1 3
1 3 1 6
1 4 1 10
2 3 3 1
2 4 3 5
3 4 6 2

Sample Output 1

4

Notes

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

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

Tổng chi phí đổi màu ~= 3 + 1 = 4~.

Khi đó ô tô có thể di chuyển theo con đường: ~1 \rightarrow 2 \rightarrow 3 \rightarrow 4~ hoặc ~1 \rightarrow 2 \rightarrow 4~.