Vé Tham Quan

Bessie đang leo một con đường mòn có $N$ trạm kiểm tra, được đánh số từ $1$ đến $N$. Có $K$ vé có thể mua. Vé thứ $i$ được bán tại trạm $c_i$ với giá $p_i$ và cho phép Bessie đi vào tất cả các trạm trong đoạn $[a_i,b_i]$.

Trước khi bước vào bất kỳ trạm nào, Bessie phải đã mua ít nhất một vé cho phép đi vào trạm đó. Khi đã có quyền đi vào một trạm, cô có thể quay lại đó bất cứ lúc nào. Bessie có thể di chuyển tự do giữa các trạm mà cô có quyền đi vào.

Với mỗi trạm bắt đầu $i$ ($1\le i\le N$), hãy xác định chi phí tối thiểu để Bessie có thể đi đến được cả trạm $1$ và trạm $N$, hoặc xuất $-1$ nếu không thể.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $N$ và $K$ ($1\le N,K\le {10}^5$).
• $K$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $c_i$, $p_i$, $a_i$, $b_i$ ($1\le c_i,a_i,b_i\le N$; $1\le p_i\le {10}^9$), mô tả một vé được bán tại trạm $c_i$ với giá $p_i$ cho phép đi vào các trạm từ $a_i$ đến $b_i$.

Dữ liệu ra

Gồm $N$ dòng, dòng thứ $i$ chứa chi phí tối thiểu để từ trạm $i$ có thể đi đến cả trạm $1$ và trạm $N$, hoặc $-1$ nếu không thể.

Ràng buộc

• $1\le N,K\le {10}^5$
• $1\le c_i,a_i,b_i\le N$
• $1\le p_i\le {10}^9$
• Test 1-7: $N,K\le 1000$
• Test 8-19: Không có ràng buộc bổ sung

Ví dụ

Ghi chú

Bessie bắt đầu tại một trạm và cần mua các vé tại các trạm mà cô có quyền đi vào để mở rộng phạm vi. Mục tiêu là phủ được cả trạm $1$ và trạm $N$ với tổng chi phí nhỏ nhất.