관광 명소 점수

가상의 나라 만테이브에는 1번부터 $n$번까지 번호가 매겨진 도시 $n$개가 있습니다. 도시들은 2차원 좌표 평면 위에 있으며, $i$번 도시의 좌표는 $(x_i, y_i)$입니다. 같은 위치에 있는 도시는 없습니다.

1번부터 $m$번까지 번호가 매겨진 고속도로 $m$개가 있습니다. 고속도로 $j$는 서로 다른 두 도시 $u_j$와 $v_j$를 잇는 선분이며, 명소 지점이 $a_j$개 있습니다. 고속도로끼리는 도시가 아닌 곳에서 교차하지 않습니다. 또한 양 끝 도시가 아닌 다른 도시를 지나는 고속도로는 없고, 두 도시를 잇는 고속도로는 최대 하나입니다.

만테이브 관광부는 명소로 삼을 도시들의 부분집합을 고르려고 합니다. 부관광부는 선택한 도시 쌍이 명소 지점이 많은 고속도로로 연결되어 있기를 바랍니다. 공집합이 아닌 도시 부분집합 $S$의 관광 점수는 다음과 같이 정의합니다.

$a < b$인 모든 쌍 $(a, b)$에 대해 도시 $a$와 $b$가 모두 $S$에 속하고 고속도로로 연결되어 있으면, 그 고속도로의 명소 지점 수를 점수에 더합니다. $f(S)$는 도시 $a$와 $b$가 모두 $S$에 속하지만 고속도로로 연결되지 않은 쌍 $(a, b)$($a < b$)의 개수입니다. 점수에서 $10^6 \times f(S)^2$을 뺍니다.

예를 들어 $n = 3$이고, 1번과 2번 도시가 명소 지점 10개인 고속도로로 연결되어 있고, 2번과 3번 도시가 명소 지점 20개인 고속도로로 연결되어 있으며, 1번과 3번 도시는 연결되어 있지 않다고 합시다. $\{1\}$의 관광 점수는 $0$입니다. $\{1, 2\}$의 점수는 $10 - 10^6 \times 0^2 = 10$입니다. $\{2, 3\}$의 점수는 $20$입니다. $\{1, 2, 3\}$의 점수는 $10 + 20 - 10^6 \times 1^2 = -999970$입니다.

공집합이 아닌 도시 부분집합 $S$ 가운데 관광 점수의 최댓값을 구하세요.

첫째 줄에 정수 $n$과 $m$($1 \le n \le 100000$, $0 \le m \le 300000$)이 주어집니다. 다음 $n$개 줄에는 각각 $x_i$와 $y_i$($0 \le x_i, y_i \le 10^9$)가 주어집니다. 다음 $m$개 줄에는 각각 $u_j$, $v_j$, $a_j$($1 \le u_j < v_j \le n$, $0 \le a_j \le 10^6$)가 주어집니다. 고속도로는 문제에서 제시한 조건을 만족합니다.

공집합이 아닌 도시 부분집합들의 관광 점수 중 최댓값을 정수 하나로 출력하세요.