Tickets

문제

Bessie is going on a hiking excursion! The trail that she is currently traversing consists of $NN$ checkpoints labeled $1\dots N1\backslash ldots\; N$ ($1\le N\le {10}^{5}1\backslash le\; N\backslash le\; 10^5$).

There are $KK$ ($1\le K\le {10}^{5}1\backslash le\; K\backslash le\; 10^5$) tickets available for purchase. The $ii$-th ticket can be purchased at checkpoint $c_{i}c\_i$ ($1\le c_i\le N1\backslash le\; c\_i\backslash le\; N$) for price $p_{i}p\_i$ ($1\le p_i\le {10}^{9}1\backslash le\; p\_i\backslash le\; 10^9$) and provides access to all of checkpoints $[a_i,b_i][a\_i,b\_i]$ ($1\le a_i\le b_i\le N1\backslash le\; a\_i\backslash le\; b\_i\backslash 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 two checkpoints to which she has access, regardless of whether their labels differ by 1 or not.

For each of $i\in [1,N]i\backslash in\; [1,N]$, output the minimum total price required to purchase access to both checkpoints $11$ and $NN$ if Bessie initially has access to only checkpoint $ii$. If it is impossible to do so, print $-1-1$ instead.

입력

The first line contains $NN$ and $KK$.

Each of the next $KK$ lines contains four integers $c_{i}c\_i$, $p_{i}p\_i$, $a_{i}a\_i$, and $b_{i}b\_i$ for each $1\le i\le K1\backslash le\; i\backslash le\; K$.

출력

$NN$ lines, one for each checkpoint.