Tickets
Bessie is going on a hiking excursion! The trail that she is currently traversing consists of n checkpoints labeled 1..n.
There are k tickets available for purchase. The i-th ticket can be purchased at checkpoint c[i] for price p[i] and provides access to all of checkpoints [a[i], b[i]]. Before entering any checkpoint, Bessie must have purchased a ticket that allows access to that checkpoint. Once Bessie has access to a checkpoint, she may return to it at any point in the future. She may travel between two checkpoints to which she has access, regardless of whether their labels differ by 1 or not.
For each of i ∈ [1, n], output the minimum total price required to purchase access to both checkpoints 1 and n if Bessie initially has access to only checkpoint i. If it is impossible to do so, print −1 instead.
Input
The first line contains n (1 ≤ n ≤ 10^5) and k (1 ≤ k ≤ 10^5).
Each of the next k lines contains four integers c[i] (1 ≤ c[i] ≤ n), p[i] (1 ≤ p[i] ≤ 10^9), a[i] and b[i] (1 ≤ a[i] ≤ b[i] ≤ n) for each i (1 ≤ i ≤ k).
Output
Print n lines, one for each checkpoint.
Example
If Bessie starts at checkpoint i = 4, then one way for Bessie to purchase access to checkpoints 1 and n is as follows:
Purchase the first ticket at checkpoint 4, giving Bessie access to checkpoints 2 and 3.
Purchase the third ticket at checkpoint 2, giving Bessie access to checkpoint 7.
Return to checkpoint 4 and purchase the second ticket, giving Bessie access to checkpoints 5 and 6.
Purchase the fourth ticket at checkpoint 6, giving Bessie access to checkpoint 1.