Hiking Tickets

Bessie is on a hiking trip. Her route consists of N checkpoints numbered from \(1\) to \(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 bought at checkpoint \(c_i\) at a price of \(p_i\) (\(1 \le p_i \le 10^9\)), and it allows Bessie to enter every checkpoint in the interval \([a_i, b_i]\) (\(1 \le a_i \le b_i \le N\)).

Before entering any checkpoint, Bessie must have already purchased a ticket that permits her entry. Once she gains access to a checkpoint, she may return to it at any later time.

For each \(i\) with \(1 \le i \le N\), assume that Bessie initially has access only to checkpoint \(i\). Determine the minimum total cost required so that she can eventually enter both checkpoint \(1\) and checkpoint \(N\). If it is impossible, output \(-1\).

inputFormat

The first line contains two integers \(N\) and \(K\). Each of the next \(K\) lines contains four integers \(c_i\), \(p_i\), \(a_i\), and \(b_i\) describing a ticket.

outputFormat

Output \(N\) lines. The \(i\)th line should contain the minimum total cost needed to eventually have access to both checkpoint \(1\) and checkpoint \(N\), starting with only checkpoint \(i\) initially accessible. If it is impossible, output \(-1\).

sample

3 3
2 5 1 3
3 4 2 3
1 3 1 2

8
5
9