Hai GPS Đối Đầu

Xe của FJ có hai hệ thống GPS, mỗi hệ thống đánh giá thời gian di chuyển trên mỗi con đường khác nhau. FJ cần đi từ ngã tư $1$ (nhà) đến ngã tư $N$ (nông trại).

Khi FJ đi qua một con đường mà không nằm trên đường đi ngắn nhất (đến $N$) theo GPS nào đó, GPS đó sẽ phàn nàn 1 lần. Nếu cả hai GPS đều phàn nàn trên cùng một đường, tổng phàn nàn là 2.

Hãy tìm đường đi từ $1$ đến $N$ sao cho tổng số lần phàn nàn là nhỏ nhất.

Dữ liệu vào

• Dòng đầu tiên: hai số nguyên $N$ và $M$.
• $M$ dòng tiếp theo: mỗi dòng chứa $A_i$, $B_i$, $P_i$, $Q_i$ — đường một chiều từ $A_i$ đến $B_i$ với thời gian $P_i$ theo GPS 1 và $Q_i$ theo GPS 2.

Dữ liệu ra

Một số nguyên duy nhất — tổng số lần phàn nàn tối thiểu.

Ràng buộc

• $2\le N\le 10000$
• $1\le M\le 50000$
• $1\le P_i,Q_i\le 100000$
• Có thể có nhiều đường nối cùng một cặp ngã tư.
• Luôn tồn tại đường đi từ $1$ đến $N$.

Ví dụ