돛단배 항해

곰돌이 푸가 티거와 함께 돛단배를 타고 항해를 떠났습니다. 티거는 노련한 뱃사람이라 배를 조종하고, 뭍에서만 지내던 푸는 조금 겁을 냅니다. 배가 진행 방향을 바꿀 때마다 바람의 힘으로 배가 기우는 각도(경사)가 달라집니다. 그럴 때마다 푸는 큰 소리로 외치는데, 경사가 크게 바뀔수록 더 크게 소리치지만 그만큼 더 짜릿한 추억이 됩니다. 항해에서 푸가 느끼는 짜릿함의 총합은 이어지는 두 구간을 지날 때 생기는 경사 변화량의 제곱을 모두 더한 값입니다. 이 값을 최대로 만들도록 티거를 도와주세요.

항해는 출발지 Piękna Góra에서 시작해 도착지 Sztynort에서 끝납니다. 방향 전환은 정해진 부표에서만 할 수 있습니다. 각 부표에서는 정해진 항로로만 이동할 수 있고, 모든 항로는 언제나 지금 있는 부표보다 번호가 큰 부표로만 이어집니다. 출발지 Piękna Góra에는 $1$번 부표가, 도착지 Sztynort에는 $n$번 부표가 있습니다. 두 부표를 잇는 각 항로 구간에는 입력으로 주어지는 고정된 경사 값이 있습니다. 배는 항구를 드나들 때 엔진으로 움직여야 하므로, 출발지에서 나가는 모든 구간과 도착지로 들어오는 모든 구간의 경사는 $0$입니다.

지나간 구간들의 경사가 순서대로 $x_1, x_2, x_3, \dots, x_k$라면,

$\sum_{i=1}^{k-1}(x_i - x_{i+1})^2$

가 푸가 느끼는 짜릿함의 총합입니다. 이 합의 최댓값을 구하세요.

다음을 수행하는 프로그램을 작성하세요.

• 표준 입력에서 항로 정보를 읽습니다.
• 항해에서 얻을 수 있는 짜릿함의 최댓값을 계산합니다.
• 결과를 표준 출력에 출력합니다.

첫째 줄에 두 정수 $n$과 $m$이 공백 하나로 구분되어 주어집니다. 이때 $1 \le n \le 200000$, $1 \le m \le 500000$입니다.

이어지는 $m$개의 줄에는 각각 세 정수 $a$, $b$, $w$가 공백 하나로 구분되어 주어집니다. $a$와 $b$는 이 구간이 잇는 두 부표의 번호로 $1 \le a < b \le n$입니다. $w$는 이 구간에서 배가 기우는 경사로 $-100000 \le w \le 100000$입니다. $a = 1$(출발지)이거나 $b = n$(도착지)이면 $w = 0$입니다.

푸가 항해에서 얻을 수 있는 짜릿함의 최댓값을 나타내는 정수 하나를 출력합니다.