Bessie đang tham gia một chuyến đi bộ đường dài! Tuyến đường mà cô đang đi qua gồm \(N\) trạm kiểm soát được đánh số \(1\ldots N\) (\(1 \le N \le 10^5\)).

Có \(K\) vé (\(1 \le K \le 10^5\)) được bán. Vé thứ \(i\) có thể được mua tại trạm kiểm soát \(c_i\) (\(1 \le c_i \le N\)) với giá \(p_i\) (\(1 \le p_i \le 10^9\)), và cho phép đi vào tất cả các trạm kiểm soát trong đoạn \([a_i,b_i]\) (\(1 \le a_i \le b_i \le N\)). Trước khi đi vào bất kỳ trạm kiểm soát nào, Bessie phải mua một vé cho phép cô đi vào trạm đó. Sau khi có quyền đi vào một trạm kiểm soát, Bessie có thể quay lại trạm ấy vào bất kỳ thời điểm nào trong tương lai. Cô có thể di chuyển giữa hai trạm kiểm soát mà mình có quyền đi vào, bất kể số hiệu của chúng có chênh nhau \(1\) hay không.

Với mỗi \(i \in [1,N]\), giả sử ban đầu Bessie chỉ có quyền đi vào trạm kiểm soát \(i\). Hãy cho biết tổng chi phí nhỏ nhất để mua quyền đi vào cả trạm kiểm soát \(1\) và trạm kiểm soát \(N\). Nếu không thể làm được, hãy in ra \(-1\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(K\).

Mỗi dòng trong \(K\) dòng tiếp theo chứa bốn số nguyên \(c_i\), \(p_i\), \(a_i\) và \(b_i\), tương ứng với vé thứ \(i\) (\(1 \le i \le K\)).

Dữ liệu ra

In ra \(N\) dòng, mỗi dòng ứng với một trạm kiểm soát.

Phân nhóm

• Các test 1–7 thỏa mãn \(N,K \le 1000\).
• Các test 8–19 không có ràng buộc bổ sung.

Ví dụ

7 6
4 1 2 3
4 10 5 6
2 100 7 7
6 1000 1 1
5 10000 1 4
6 100000 5 6

-1
-1
-1
1111
10100
110100
-1

Nguồn

USACO 2021 December Contest, Platinum — Tickets. Tác giả: Benjamin Qi.

https://usaco.org/index.php?page=viewproblem2&cpid=1164