공항 대기 최소화

데이비드는 세계 곳곳을 여행하려고 한다. 방문할 수 있는 나라는 $n$개이고, 탈 수 있는 항공편은 $m$개다. $i$번 항공편은 시각 $s_i$에 나라 $a_i$를 출발해 시각 $e_i$에 나라 $b_i$에 도착한다.

데이비드는 시각 $0$에 나라 $1$의 공항에 있고, 나라 $n$까지 가려고 한다. 이동에 걸리는 전체 시간은 신경 쓰지 않지만, 공항에서 기다리는 것은 몹시 싫어한다. 공항에서 $t$만큼 기다리면 짜증이 $t^2$만큼 쌓인다. 시각 $0$부터 첫 항공편이 출발할 때까지 나라 $1$의 공항에서 보내는 시간도 기다린 시간에 들어간다.

짜증의 총합이 가장 작은 일정을 구하라.

첫째 줄에 정수 $n$과 $m$이 공백으로 구분되어 주어진다. ($2 \le n \le 200\,000$, $1 \le m \le 200\,000$)

다음 $m$개의 줄에는 네 정수 $a_i$, $b_i$, $s_i$, $e_i$가 공백으로 구분되어 주어진다. ($1 \le a_i, b_i \le n$, $0 \le s_i \le e_i \le 10^6$) 이는 시각 $s_i$에 나라 $a_i$를 출발해 시각 $e_i$에 나라 $b_i$에 도착하는 항공편을 뜻한다.

출발 나라와 도착 나라가 같은 항공편도 있을 수 있다.

출발 시각이 같은 두 항공편은 없고, 도착 시각이 같은 두 항공편도 없다. 또 어떤 항공편의 도착 시각이 다른 항공편의 출발 시각과 같은 경우도 없다. 나라 $n$에 도착하는 일정은 항상 존재한다.

짜증의 총합의 최솟값을 한 줄에 출력한다.

첫 번째 예제에서 짜증이 가장 적은 일정은 다음과 같다.

• 입력의 다섯째 항공편. 나라 $1$에서 나라 $2$로, 시각 $3$에 출발해 시각 $8$에 도착한다.
• 셋째 항공편. 나라 $2$에서 나라 $1$로, 시각 $9$에 출발해 시각 $12$에 도착한다.
• 일곱째 항공편. 나라 $1$에서 나라 $3$으로, 시각 $13$에 출발해 시각 $27$에 도착한다.
• 여덟째 항공편. 나라 $3$에서 나라 $5$로, 시각 $28$에 출발해 시각 $100$에 도착한다.

네 번의 기다림에서 쌓이는 짜증은 각각 $3^2$, $1^2$, $1^2$, $1^2$이고, 총합은 $12$다. 더 빨리 도착하는 일정도 있지만 짜증의 총합은 더 크다.