티켓

Bessie는 하이킹 여행을 떠난다. 지금 지나고 있는 산책로에는 1부터 $N$까지 번호가 붙은 체크포인트 $N$개가 있다 ($1\le N\le 10^5$).

구매할 수 있는 티켓은 $K$개이다 ($1\le K\le 10^5$). $i$번째 티켓은 체크포인트 $c_i$ ($1\le c_i\le N$)에서 가격 $p_i$ ($1\le p_i\le 10^9$)에 살 수 있으며, 구매하면 $[a_i,b_i]$ ($1\le a_i\le b_i\le N$) 구간에 속한 모든 체크포인트에 접근할 수 있다. 체크포인트에 들어가기 전에 Bessie는 그 체크포인트에 접근할 수 있는 티켓을 미리 구매해야 한다. 한 번 접근 권한을 얻은 체크포인트는 이후 언제든 다시 방문할 수 있다. 접근 권한이 있는 두 체크포인트 사이는 번호 차이와 상관없이 이동할 수 있다.

각 $i\in[1,N]$에 대해, Bessie가 처음에 체크포인트 $i$에만 접근할 수 있다고 하자. 이때 체크포인트 1과 체크포인트 $N$에 모두 접근하기 위해 필요한 티켓 가격 합의 최솟값을 출력한다. 불가능하면 -1을 출력한다.

첫 줄에 $N$과 $K$가 주어진다.

다음 $K$개의 줄에는 각각 정수 $c_i$, $p_i$, $a_i$, $b_i$가 주어진다.

$N$개의 줄을 출력한다. 각 줄은 체크포인트 하나에 대응한다.