Problem Description

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$.

Input Format

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 Format

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

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

Hint

[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