Tickets

Bessie is going on a hiking excursion. The trail she is currently traversing consists of $N$ checkpoints labeled $1\ldots N$ ($1\le N\le 10^5$).

There are $K$ tickets available for purchase ($1\le K\le 10^5$). The $i$-th ticket can be purchased at checkpoint $c_i$ ($1\le c_i\le N$) for price $p_i$ ($1\le p_i\le 10^9$) and provides access to all checkpoints in $[a_i,b_i]$ ($1\le a_i\le b_i\le N$). 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 any two checkpoints to which she has access, whether or not their labels differ by 1.

For each $i\in[1,N]$, suppose Bessie initially has access to only checkpoint $i$. Output the minimum total price required to purchase access to both checkpoints $1$ and $N$. If it is impossible, output -1.

The first line contains $N$ and $K$.

Each of the next $K$ lines contains four integers $c_i$, $p_i$, $a_i$, and $b_i$.

Output $N$ lines, one for each checkpoint.