P7984 [USACO21DEC] Tickets P

Bessie is going on a hiking trip! The route she is currently traveling consists of $N$ checkpoints numbered $1\ldots N$ ($1\le N\le 10^5$). There are $K$ ($1\le K\le 10^5$) tickets available for purchase. Ticket $i$ can be bought at checkpoint $c_i$ ($1\le c_i\le N$) for price $p_i$ ($1\le p_i\le 10^9$), and it allows entry to all checkpoints in $[a_i,b_i]$ ($1\le a_i\le b_i\le N$). Before entering any checkpoint, Bessie must have already bought a ticket that allows her to enter that checkpoint. Once Bessie can travel to a checkpoint, she can return to that checkpoint at any time in the future. For each $i\in [1,N]$, if Bessie can initially only enter checkpoint $i$, output the minimum total cost required to be able to enter checkpoints $1$ and $N$. If it is impossible, output $-1$.

The first line contains $N$ and $K$. The next $K$ lines each describe one ticket. For each $1\le i\le K$, line $i$ contains four integers $c_i$, $p_i$, $a_i$, and $b_i$.

Output $N$ lines. On each line, output the answer for one starting checkpoint.

[Sample Explanation] If Bessie starts from checkpoint $i=4$, then one way to buy tickets to be able to enter checkpoints $1$ and $N$ is: Buy the first ticket at checkpoint $4$, allowing Bessie to enter checkpoints $2$ and $3$. Buy the third ticket at checkpoint $2$, allowing Bessie to enter checkpoint $7$. Go back to checkpoint $4$ and buy the second ticket, allowing Bessie to enter checkpoints $5$ and $6$. Buy the fourth ticket at checkpoint $6$, allowing Bessie to enter checkpoint $1$. [Constraints] - Test cases 1-7 satisfy $N, K\le 1000$. - Test cases 8-19 have no additional constraints. Translated by ChatGPT 5